The challenge
Among many points, find the two closest ones. Checking all pairs is quadratic. A divide and conquer scheme does far better by exploiting geometry in the merge.
Divide and conquer
Sort points by x and split them into a left half and a right half. Recursively find the closest pair in each half. Let the smaller of the two distances be the current best.
- The answer is either fully inside a half,
- or it crosses the dividing line.
The strip trick
Crossing pairs must lie within the current best distance of the dividing line, so collect points in that vertical strip. Sort the strip by y coordinate. A geometric fact says each point only needs to be compared with a small constant number of following points in the strip, because more than that cannot fit within the best distance.
- This bounds the merge to linear work per level.
Putting it together
With the recursion splitting the set and the strip merge staying linear, the total cost grows only mildly faster than linear, far beating the naive all pairs check.
Key idea
Closest pair splits points by x, recurses on each half, and merges by scanning only a narrow strip near the cut where each point meets a constant number of neighbors, keeping the merge linear.