I have been working for some time on data structures for
maintaining closest pairs of objects, as objects are dynamically
inserted or deleted. Here "objects" might be any of a number of
things (points in a vector space; clusters of points; DNA
sequences; ridges, valleys, and other features of the roof of a
building...) and "closest" may have its usual geometric meaning or
may be determined by some arbitrary function of the objects.
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, .