Closest Pair Data Structures: Methods

We have designed, analyzed, and implemented several different closest pair data structures. See the papers or source code for more detail. We analyze the times in terms of two parameters: n, the number of objects in the set, and Q, the time per operation to perform insertions, deletions, and nearest neighbor queries in a dynamic set of objects. Our implementations use trivial nearest neighbor searching (just examine the distances to each objects), for which Q=O(n).

Previously known were:

New closest pair data structures:

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