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:
“I like sometimes to take rank hold on life and spend my day more as the animals do. Perhaps I have owed to this employment and to hunting, when quite young, my closest acquaintance with Nature. They early introduce us to and detain us in scenery with which otherwise, at that age, we should have little acquaintance.”
—Henry David Thoreau (1817–1862)
“The Republican convention, an event with the intellectual content of a Guns’n’Roses lyric attended by every ofay insurance broker in America who owns a pair of white shoes.”
—P.J. (Patrick Jake)
“Wonderful “Force of Public Opinion!” We must act and walk in all points as it prescribes; follow the traffic it bids us, realise the sum of money, the degree of “influence” it expects of us, or we shall be lightly esteemed; certain mouthfuls of articulate wind will be blown at us, and this what mortal courage can front?”
—Thomas Carlyle (1795–1881)
“The problem ... is emblematic of what hasn’t changed during the equal opportunity revolution of the last 20 years. Doors opened; opportunities evolved. Law, institutions, corporations moved forward. But many minds did not.”
—Anna Quindlen (b. 1952)