Closest Pair Theory

Problem

Given n points in 2D, find the pair with minimum Euclidean distance. A brute force O(n^2) approach compares all pairs; divide and conquer reduces this to O(n log n) by pruning comparisons via geometric constraints in a narrow vertical strip around the splitting line.

Algorithm Phases

1. Sort points by x once (preprocessing).
2. Recursively split by median x into left/right subsets.
3. Compute best distances dl, dr from halves.
4. delta = min(dl, dr); collect strip points with |x - midX| <= delta.
5. Sort strip by y and compare each to next ≤ 7 points.
6. Answer = min(delta, best strip distance).

Why At Most 7 Comparisons?

Packing argument: Inside a delta × 2delta rectangle you cannot pack more than 8 points mutually farther than delta apart. After y-sorting, only the next 7 neighbors can beat delta; further points exceed delta vertically.

Pseudocode

1function closestPair(points):
2  sort points by x
3  return recursive(points)
4function recursive(P):
5  if |P| <= 3: return bruteForce(P)
6  mid = |P|/2; L = P[0:mid]; R = P[mid:]
7  d = min(recursive(L), recursive(R))
8  strip = points within d of mid line
9  return min(d, stripClosest(strip, d))

Key Insights

• Spatial ordering drastically reduces candidate pairs.
• Strip stage mirrors merge step conceptually (ordered by y).
• Packing bound enables constant comparisons per point.
• Illustrates multi-axis ordering synergy (x then y).

Edge Considerations

• Duplicate points: distance 0 early exit.
• n ≤ 3 handled by brute force fallback.
• Stable merge-by-y maintains consistent global ordering.