The Problem
Given $n$ points in the plane, find the pair with the smallest Euclidean distance between them. Brute force checks every pair — $O(n^2)$. This part derives an $O(n \log n)$ divide-and-conquer algorithm, one of the field's classic results (Shamos and Hoey, 1975) and one of the earliest demonstrations that divide and conquer applies to genuinely geometric (not just combinatorial) problems.
The Divide-and-Conquer Structure
- Presort all points by $x$-coordinate once, up front (not on every recursive call — see the invariant below).
- Divide: split the point set at the median $x$-coordinate into a left half $L$ and a right half $R$.
- Conquer: recursively find the closest pair within $L$ alone and within $R$ alone. Let $\delta$ be the smaller of the two distances found.
- Combine: the true closest pair is either entirely within $L$, entirely within $R$, or split across the dividing line — one point in each half, and closer together than $\delta$. Only this third case needs new work.
The Strip Check
Any cross-boundary pair closer than $\delta$ must both lie within $\delta$ of the dividing line — a vertical strip of width $2\delta$. Collect the points in that strip, sort them by $y$-coordinate, and for each point, only compare it against the next few points in that $y$-sorted order.
Core Insight (the packing argument): for any point $p$ in the strip, only a constant number of other strip points can possibly be closer than $\delta$ to it — not $O(n)$. Divide the $\delta \times \delta$ square directly above $p$ (within the strip) into six $\frac{\delta}{2} \times \frac{\delta}{2}$ boxes. Two points inside the same box are at most $\frac{\delta}{\sqrt2} \approx 0.707\delta$ apart — closer than $\delta$ — but if either half's recursive closest-pair distance is already $\delta$, no two points within the same half can be that close. Since each box lies entirely within one half of the strip (or straddles the dividing line, which is fine — the argument only needs one point of the pair per box), each box holds at most one point from each half, and there are only 6 boxes: at most 6 other points ever need checking, no matter how large $n$ is. In practice, checking against the next 7 points in $y$-order (a small constant slack over the tight bound) is a common, simpler-to-verify implementation choice.
This constant-work-per-point bound is what makes the combine step run in $O(n)$ (given the strip is already sorted by $y$), rather than $O(n \log n)$ or worse — and it's why the recurrence
$$ T(n) = 2T(n/2) + O(n) $$
solves to $O(n \log n)$ by the Master theorem, matching the sorting lower bound established for convex hulls in the previous part (closest pair, like convex hull, reduces from sorting — the same parabola-mapping argument applies).
The Presorting Invariant
Re-sorting points by $y$-coordinate on every recursive call would cost $O(n \log n)$ per level of recursion, giving $O(n \log^2 n)$ overall — still correct, but not optimal. The standard fix: sort by $x$ once at the top level, and pass a second list, already sorted by $y$, down through the recursion — partitioning that $y$-sorted list into left/ right halves during the divide step preserves the sort order of each half in $O(n)$ per level (a merge-like partition), avoiding any re-sorting. This is the same "presort once, maintain order through recursion" trick that appears throughout divide-and-conquer algorithms (and again in Part 6's sweep line).
Duplicate Points
If two input points share the same coordinates, the closest-pair distance is exactly $0$ — handled automatically by the algorithm above (no special case needed), but worth stating explicitly as a policy, since a distance of exactly zero is sometimes treated as an error condition by careless callers expecting distinct points.
Visualizing the Combine Step
The recursive calls certify that no same-side pair is closer than $\delta$. Only points whose horizontal distance from the median is below $\delta$ can participate in a better cross pair. Everything outside the shaded strip is eliminated by one coordinate comparison.
The constant is a consequence of packing, not a magic loop bound. Once each half has minimum separation $\delta$, a bounded rectangle cannot contain an unbounded number of relevant points. In $y$ order, stop as soon as the vertical gap reaches $\delta$; Euclidean distance can only be larger.
Implementation Invariants That Prevent Subtle Bugs
- Return both the best pair and its squared distance; take a square root only for presentation. Integer inputs then retain exact distance comparisons.
- Tag points with stable IDs. If many share the median $x$-coordinate,
x <= mid_xcannot reliably reconstruct the same left/right partition in the $y$-sorted list. - Partition the $y$-ordered list in linear time using those IDs, preserving its order for both recursive calls.
- Use brute force for two or three points. A clear base case simplifies the recursion and gives a reliable oracle for tests.
Trace the Strip
Suppose the recursive halves return $\delta=5$. A left point is two units from the median and a right point is one unit from it, with a vertical separation of three. Their distance is $\sqrt{3^2+3^2}\approx4.24$, so the pair improves the answer. If the vertical separation were already five, no horizontal separation could make the Euclidean distance less than $\delta$, so the scan could stop.
Randomized Alternatives
A different family of algorithms solves the same problem via grid hashing: pick a trial distance $\delta$, hash every point into a grid of cells $\delta \times \delta$, and check each point only against points in its own and neighboring cells. Started with the correct $\delta$ (e.g. from a random sample), this runs in expected $O(n)$ time — faster than $O(n \log n)$, but only in expectation, and only because it forgoes the deterministic worst-case guarantee that the divide-and-conquer version provides. Rabin's 1976 randomized closest-pair algorithm is the earliest example of this technique, predating widespread use of randomization elsewhere in the field.
The next part returns to convex polygons, using antipodal point pairs — found by "rotating calipers" around a hull — to compute diameter, width, and the minimum- area enclosing rectangle.
Next in the Series
In Rotating Calipers and Convex-Polygon Optimization, we'll explore computing the diameter, width, and minimum-area enclosing rectangle of a convex polygon using antipodal point pairs.