Closest pair of points problem

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.

Randomized algorithms that solve the problem in linear time are known, in Euclidean spaces whose dimension is treated as a constant for the purposes of asymptotic analysis.

time (expressed here in big O notation) that would be obtained by a naive algorithm of finding distances between all pairs of points and selecting the smallest.

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

[5] In even more restricted models of computation, such as the algebraic decision tree, the problem can be solved in the somewhat slower

time bound,[6] and this is optimal for this model, by a reduction from the element uniqueness problem.

[7][8] A linear expected time randomized algorithm of Rabin (1976), modified slightly by Richard Lipton to make its analysis easier, proceeds as follows, on an input set

The uniform sampling of pairs in the first step of the algorithm (compared to a different method of Rabin for sampling a similar number of pairs) simplifies the proof that the expected number of distances computed by the algorithm is linear.

[4] Instead, a different algorithm Khuller & Matias (1995) goes through two phases: a random iterated filtering process that approximates the closest distance to within an approximation ratio of

becomes empty: The approximate distance found by this filtering process is the final value of

Each step removes all points whose closest neighbor is at distance

is known, it can be used for the final steps of Rabin's algorithm; in these steps each grid point has a constant number of inputs rounded to it, so again the time is linear.

[3] The dynamic version for the closest-pair problem is stated as follows: If the bounding box for all points is known in advance and the constant-time floor function is available, then the expected

-space data structure was suggested that supports expected-time

When modified for the algebraic decision tree model, insertions and deletions would require

[9] The complexity of the dynamic closest pair algorithm cited above is exponential in the dimension