The closest pair of points problem or closest pair problem is a problem of computational geometry 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 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, 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 time. In even more restricted models of computation, such as the algebraic decision tree time bound, and this is optimal for this model, by a reduction from the element uniqueness problem. Both sweep line algorithms and divide-and-conquer algorithms with this slower time bound are commonly taught as examples of these algorithm design techniques.

Linear-time randomized algorithms

A linear expected time randomized algorithm of , modified slightly by Richard Lipton-dimensional Euclidean space:

1. be the minimum distance of the selected pairs.

2. , and use a hash table to collect together pairs of input points that round to the same grid point.

3. For each input point, compute the distance to all other inputs that either round to the same grid point or to another grid point within the Moore neighborhood surrounding grid points.

4. Return the smallest of the distances computed throughout this process.

to the same grid point or to adjacent grid points. 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.

Instead, a different algorithm goes through two phases: a random iterated filtering process that approximates the closest distance to within an approximation ratio becomes empty:

1. .

2. be the minimum such distance.

3. all points whose Moore neighborhood has no other points.

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.

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 expected time., and therefore such an algorithm becomes less suitable for high-dimensional problems.

dimensional space was developed by Sergey Bespamyatnikh in 1998. time per point (in the worst case).

See also

• GIS

• Nearest neighbor search

Notes