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:
“... a business career for a woman and her need for a woman’s life as wife and mother, are not enemies at all, unless we make them so, but may be the closest and most co-operative friends and supporter of each other.”
—Hortense Odlum (1892–?)
“The majority of persons choose their wives with as little prudence as they eat. They see a trull with nothing else to recommend her but a pair of thighs and choice hunkers, and so smart to void their seed that they marry her at once. They imagine they can live in marvelous contentment with handsome feet and ambrosial buttocks. Most men are accredited fools shortly after they leave the womb.”
—Edward Dahlberg (1900–1977)
“the
Decapitated exclamation points in that Other Woman’s eyes.”
—Gwendolyn Brooks (b. 1917)
“The problem of induction is not a problem of demonstration but a problem of defining the difference between valid and invalid
predictions.”
—Nelson Goodman (1906)