The all pairs trap
Finding the two closest points by checking every pair is quadratic and slow for large sets. A divide and conquer scheme does much better by splitting the points, solving each half, and combining the results carefully.
Divide and recurse
The algorithm sorts points by their horizontal coordinate, then:
- Split the set into a left half and a right half by a vertical line.
- Recursively find the closest pair within each half.
- Keep the smaller of the two distances as the current best.
The subtle part is that the true closest pair might have one point in each half, straddling the dividing line. The recursion alone cannot catch that.
The strip combine
To handle the split case, look only at points within a vertical strip whose width is the current best distance, centered on the dividing line. Sort the strip points by their vertical coordinate. A geometric packing argument shows each point only needs to be compared against a small constant number of following neighbors in that order. This keeps the combine step linear, so the whole method stays efficient.
Key idea
Recurse on each half, then scan a narrow strip around the divide where each point meets only a few neighbors, catching the cross boundary closest pair.