Closest pair of points problem

The closest pair of points problem or closest pair problem is a problem of computational geometry: given 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. 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. This is significantly faster than the 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 time. In even more restricted models of computation, such as the algebraic decision tree, the problem can be solved in the somewhat slower 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. A linear expected time randomized algorithm of , modified slightly by Richard Lipton to make its analysis easier, proceeds as follows, on an input set consisting of points in a -dimensional Euclidean space: Select pairs of points uniformly at random, with replacement, and let be the minimum distance of the selected pairs. Round the input points to a square grid of points whose size (the separation between adjacent grid points) is , and use a hash table to collect together pairs of input points that round to the same grid point. 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 of surrounding grid points.