Closest Pair of Points

Divide the plane, solve halves, then examine a narrow y-sorted strip to achieve optimal O(n log n) versus naive O(n²) brute force.

O(n log n)

Strip scan stays linear

O(n)

Auxiliary ordering by y

Divide • Recurse • Strip

Constant candidate checks

Key Mechanics

Y-sorted strip caps neighbors to 7 candidates.

Best distance delta narrows mid region.

Merge-by-y keeps strip build linear.

T(n) = 2T(n/2) + O(n)

Master Theorem ⇒ O(n log n). Linear strip merge plus constant candidate bound.