Simple randomized algorithms for closest pair problems

We present a conceptually simple, randomized incremental algorithm for finding the closest pair in a set of n points in D-dimensional space, where D ≥ 2 is a fixed constant. Much of the work reduces to maintaining a dynamic dictionary. Using dynamic perfect hashing to implement the dictionary, the closest pair algorithm runs in O(n) expected time. Alternatively, we can use balanced search trees, and stay within the algebraic computation tree model, which yields an expected running time of O(n log n). In addition to being quick on the average, the algorithm is reliable: we show that the high-probability bound increases only slightly to O(n log n/log log n) if we use hashing and even remains O(n log n) if we use trees as our dictionary implementation. Finally, we give some extensions to the fully dynamic closest pair problem, and to the k closest pair problem.