I can think of some kind of tree that divide the space, which probably gives logarithmic time complexity. I have heard about quadtrees before.