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 was among the first geometric problems which were treated at the origins of the systematic study of the computational complexity of geometric algorithms.
A naive algorithm of finding distances between all pairs of points and selecting the minimum requires O(dn2) time. It turns out that the problem may be solved in O(n log n) time in a Euclidean space or Lp space of fixed dimension d. In the algebraic decision tree model of computation, the O(n log n) algorithm is optimal. The optimality follows from the observation that the element uniqueness problem (with the lower bound of Ω(n log n) for time complexity) is reducible to the closest pair problem: checking whether the minimal distance is 0 after the solving of the closest pair problem answers the question whether there are two coinciding points.
In the computational model which assumes that the floor function is computable in constant time the problem can be solved in O(n log log n) time. If we allow randomization to be used together with the floor function, the problem can be solved in O(n) time.
Read more about Closest Pair Of Points Problem: Brute-force Algorithm, Planar Case, Dynamic Closest-pair Problem
Famous quotes containing the words closest, pair, points and/or problem:
“Many great writers have been extraordinarily awkward in daily exchange, but the greatest give the impression that their style was nursed by the closest attention to colloquial speech.”
—Thornton Wilder (1897–1975)
“You are always looking for already-felt emotions, just as you like to get an old pair of trousers back from the cleaners, which seem new when you don’t look too closely. Artists are cleaners, don’t let yourself be taken in by them. True modern works of art are made not by artists but quite simply by men.”
—Francis Picabia (1878–1953)
“If I were in the unenviable position of having to study my work my points of departure would be the “Naught is more real ...” and the “Ubi nihil vales ...” both already in Murphy and neither very rational.”
—Samuel Beckett (1906–1989)
“Like the effects of industrial pollution ... the AIDS crisis is evidence of a world in which nothing important is regional, local, limited; in which everything that can circulate does, and every problem is, or is destined to become, worldwide.”
—Susan Sontag (b. 1933)