What you're seeing
Given a cloud of points, which two are closest? Checking every pair is O(n²). Divide and conquer does better: sort the points by x, cut at the median into a left and right half, and find the closest pair in each half recursively. Let δ be the smaller of those two distances. The only pairs left unconsidered are those split across the line — and any such pair closer than δ must have both endpoints within δ of the line, in a thin vertical strip. So we only have to reconcile that strip. Watch the recursion bottom out on tiny clusters, then the strips light up as the halves merge.
The rule
closest(points sorted by x):
if ≤ 3 points: compare all pairs directly
split at median x → left, right
δ = min(closest(left), closest(right))
strip = points within δ of the split line, sorted by y
for each p in strip:
compare p to the next few points in y-order # ≤ 7 of them
update δ if any is closer
return δ
The invariant
The whole speed-up rests on a packing argument: no split-crossing pair can be closer than δ unless both of its points lie in the 2δ-wide strip — and within the strip, sorted by y, each point can have at most a constant number of others within δ. Why constant: pack points into the strip so all are ≥ δ apart (they must be, or we'd already know a closer pair within a half); a δ × 2δ box around any point can hold only a bounded number of such points (at most 8, classically). So scanning each strip point against its next ~7 neighbors in y-order is enough — and the moment a neighbor is more than δ farther in y, we can stop, because nothing beyond it can be within δ. Because we never skip a strip pair that could be closer, the answer is exactly the true closest pair (this entry's test confirms it against brute force).
The cost
The recurrence is T(n) = 2·T(n/2) + O(n) — the same as merge sort — giving O(n log n), provided the strip is processed in linear time (pre-sort by y once, or merge y-orders up the recursion, so each level is O(n)). That matches the known lower bound for the problem in the comparison model, so it's optimal. A clever randomized algorithm (Rabin; Khuller–Matias) even reaches expected O(n) using a grid keyed on the current δ.
In the wild
Closest-pair is a foundational computational-geometry primitive and a classic teaching example of divide and conquer (Shamos & Hoey, 1975; Bentley & Shamos). The underlying question — nearest neighbors among many points — drives collision detection in games and simulation, clustering and anomaly detection, map and GIS queries ("nearest station"), and de-duplication of near-identical records. At higher dimensions the exact strip trick fades and the torch passes to spatial indexes (k-d trees, ball trees) and, when dimensions get large, to approximate methods like LSH.
Try this
Step through the start: small clusters get solved by brute force first, then each merge draws its split line and shaded strip. Watch how few points ever fall inside the strip — that thinness is the whole algorithm. Add more Points and compare the comparison count in the readout to n(n−1)/2; the gap widens fast.
References
- Shamos, M. I. & Hoey, D. "Closest-point problems." 16th IEEE Symposium on Foundations of Computer Science (FOCS), 1975.
- Bentley, J. L. & Shamos, M. I. "Divide-and-conquer in multidimensional space." STOC, 1976.
- Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §33.4 (Finding the closest pair of points). MIT Press, 2022.