Simple Randomized Algorithms for Closest Pair Problems.
Mordecai J. Golin, Rajeev Raman, Christian J. Schwarz, Michiel Smid · Max Planck Institute for Plasma Physics · 1993
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 \\geq 2$ is a fixed constant. Using dynamic perfect hashing, the algorithm runs in $O(n)$ expected time. In addition to being quick on the average, this algorithm is reliable: we show that it runs in $O(n \\log n / \\log\\log n)$ time with high probability.