The closest pair of points problem, or closest pair problem, is a computational geometry problem in which, given n points in a metric space, the goal is to 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 treated at the origins of the systematic study of the computational complexity of geometric algorithms.
Facts
Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Classification
Design Technique Connections
Sources
1. Closest Pair of Points Algorithm (Wikipedia)
Wikipedia infobox: time complexity linearithmic
linearithmic
Wikipedia: design technique divide-and-conquer
divide-and-conquer
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.