Closest pair of points problem

The closest pair of points problem or closest pair problem is a problem of computational geometry: given $n$ points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean plane^[1] was among the first geometric problems that were treated at the origins of the systematic study of the computational complexity of geometric algorithms.

Time bounds

Randomized algorithms that solve the problem in linear time are known,^[2]^[3] significantly more quickly than the $O(n^{2})$ time (expressed here in big O notation) that would be obtained by a naive algorithm of finding distances between all pairs of points in a space of dimension $d$ and selecting the minimum.

It is also possible to solve the problem without randomization, in random-access machine models of computation with unlimited memory that allow the use of the floor function, in near-linear $O(n\log \log n)$ time.^[4] In even more restricted models of computation, such as the algebraic decision tree, the problem can be solved in the somewhat slower $O(n\log n)$ time bound, using either plane sweep or geometric divide and conquer methods,^[5]^[6] and this is optimal for this model, by a reduction from the element uniqueness problem.

Dynamic closest-pair problem

The dynamic version for the closest-pair problem is stated as follows:

Given a dynamic set of objects, find algorithms and data structures for efficient recalculation of the closest pair of objects each time the objects are inserted or deleted.

If the bounding box for all points is known in advance and the constant-time floor function is available, then the expected $O(n)$ -space data structure was suggested that supports expected-time $O(\log n)$ insertions and deletions and constant query time. When modified for the algebraic decision tree model, insertions and deletions would require $O(\log ^{2}n)$ expected time.^[7] The complexity of the dynamic closest pair algorithm cited above is exponential in the dimension $d$ , and therefore such an algorithm becomes less suitable for high-dimensional problems.

An algorithm for the dynamic closest-pair problem in $d$ dimensional space was developed by Sergey Bespamyatnikh in 1998.^[8] Points can be inserted and deleted in $O(\log n)$ time per point (in the worst case).

Notes

^ Shamos, Michael Ian; Hoey, Dan (1975). "Closest-point problems". 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975. IEEE Computer Society. pp. 151–162. doi:10.1109/SFCS.1975.8.
^ Khuller, Samir; Matias, Yossi (1995). "A simple randomized sieve algorithm for the closest-pair problem". Information and Computation. 118 (1): 34–37. doi:10.1006/inco.1995.1049. MR 1329236.
^ Lipton, Richard (24 September 2011). "Rabin Flips a Coin". Gödel's Lost Letter and P=NP.
^ Fortune, Steve; Hopcroft, John (1979). "A note on Rabin's nearest-neighbor algorithm". Information Processing Letters. 8 (1): 20–23. doi:10.1016/0020-0190(79)90085-1. MR 0515507.
^ Clarkson, Kenneth L. (1983). "Fast algorithms for the all nearest neighbors problem". 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983. IEEE Computer Society. pp. 226–232. doi:10.1109/SFCS.1983.16.
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "33.4: Finding the closest pair of points". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 957–961. ISBN 0-262-03293-7.
^ Golin, Mordecai; Raman, Rajeev; Schwarz, Christian; Smid, Michiel (1998). "Randomized data structures for the dynamic closest-pair problem". SIAM Journal on Computing. 27 (4): 1036–1072. doi:10.1137/S0097539794277718. MR 1622005.
^ Bespamyatnikh, S. N. (1998). "An optimal algorithm for closest-pair maintenance". Discrete & Computational Geometry. 19 (2): 175–195. doi:10.1007/PL00009340. MR 1600047.

Closest pair of points problem

Time bounds

Dynamic closest-pair problem

See also

Notes

Further reading