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:
“The universe is not rough-hewn, but perfect in its details. Nature will bear the closest inspection; she invites us to lay our eye level with the smallest leaf, and take an insect view of its plain. She has no interstices; every part is full of life.”
—Henry David Thoreau (1817–1862)
“There are two kinds of truth; the truth that lights the way and the truth that warms the heart. The first of these is science, and the second is art.... Without art science would be as useless as a pair of high forceps in the hands of a plumber. Without science art would become a crude mess of folklore and emotional quackery.”
—Raymond Chandler (1888–1959)
“There are good points about all such wars. People forget self. The virtues of magnanimity, courage, patriotism, etc., etc., are called into life. People are more generous, more sympathetic, better, than when engaged in the more selfish pursuits of peace.”
—Rutherford Birchard Hayes (1822–1893)
“Great speeches have always had great soundbites. The problem now is that the young technicians who put together speeches are paying attention only to the soundbite, not to the text as a whole, not realizing that all great soundbites happen by accident, which is to say, all great soundbites are yielded up inevitably, as part of the natural expression of the text. They are part of the tapestry, they aren’t a little flower somebody sewed on.”
—Peggy Noonan (b. 1950)