The closest pair problem is a problem in computational geometry where the objective is to find a pair of points having the minimum euclidean distance between them.
Input: N points in Euclidean space
Output: A pair of points having the smallest Euclidean distance between them
Brute force algorithm for this problem takes O(n2) time, finding the smallest distance between all nC2 = n(n-1)/2 pairs of points and can be described as follows:
However, the closest pair problem can be solved in O(nlogn) using a divide and conquer approach as follows:
- Sort points according to x-coordinate.
- Recursively find the closest pairs in the left and right halves. Let ‘d’ be the smallest distance found so far.
- Find all the points whose x-coordinate is closer to the middle line (assume a vertical line passing through the middle point) than d.
- Find the closest pair among the points found in the previous step. It can be proven geometrically that each point needs to be compared to only the next 7 points in the worst case so this step takes only linear time.
- Return the closest pair from the pairs found in steps 2 and 4.
Take a look at the C++ implementation.
Try your hand at problem CLOPPAIR, which uses this idea.