My methods generally assume the existence of another data
structure, for finding the closest object in a dynamic set to a
given query object. This can be solved in general in O(*n*)
distance computations per query (just keep a list of all objects,
and try them all) but for objects arising in computational geometry
better solutions are possible (k-D trees for points, more
complicated range search data structures for other geometric
objects).

David Eppstein, Information & Computer Science, UC Irvine, .