Research Projects: Closest Pairs

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).

Methods and Summary of Results

Applications

Papers

Talks and Talk Slides

Source Code

Experimental Data

Links to Related Web Sites


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