Given n points on a plane, which two are nearest each other? Checking every pair
directly costs O(n²) — for 12 points, 66 distance comparisons. The divide-and-conquer
answer sorts the points by x, splits them in half, solves each half recursively, and
then does the one non-obvious step: the true closest pair might not live inside either half at
all — it might straddle the dividing line, one point on each side. Rather than re-checking every
cross-half pair (which would cost the O(n²) the split was supposed to avoid), only a
narrow vertical strip around the line needs checking, and only a handful of comparisons per point
inside it.
This opens a new Geometry category, distinct from the site's existing Convex Hull entries. Convex Hull asks "what's the boundary of this point set," built on one primitive — the cross product, which way does a path turn. This page asks a genuinely different question, "which two points are nearest," built on a different primitive — Euclidean distance — and a different kind of divide-and-conquer: not merging boundaries, but propagating a shrinking bound (the best distance found so far) up through the recursion and using it to decide how much of the strip actually needs checking.
Twelve points, sorted by x and deliberately arranged so the true closest
pair — F and G — sits on opposite sides of the very last split.
Press Step or Run to watch the recursion: inactive points dim out,
the current strip (points close enough to the dividing line to matter) highlights, and each strip
comparison is checked against the best distance found so far. The final line drawn is the actual
answer — watch what it takes to displace whatever "best so far" the two halves handed up.
Sort once by x, then recurse: split the sorted list in half, solve the left half,
solve the right half. Each side returns its own best distance, d = the smaller of the
two. If the real closest pair on the whole set is entirely within one side, that recursive call
already found it — done. The only case left is a pair that crosses the dividing line, one point in
each half.
Here's the fact that makes the crossing case cheap instead of another O(n²) scan:
if two points on opposite sides of the line are closer to each other than d, both of
them must individually lie within distance d of the line itself — a point farther than
d from the line is already farther than d from everything on the other
side, horizontal distance alone. So the only points worth checking for a cross-boundary pair are
the ones in a vertical strip of width 2d centered on the split — everything else is
provably too far away to matter, without ever computing its actual distance to anything.
Within that strip, sorting by y and checking each point only against the next few
neighbors (stopping the moment the y-gap alone reaches d) is enough,
for the same horizontal-distance-alone reasoning applied vertically: any two points already known to
be on the same side of the line are, by definition of d, at least d apart —
so a d-by-2d rectangle around the line can only ever hold a small number of
points regardless of how large n gets, and the inner loop below naturally stops once the
sorted y-gap alone rules out anything closer. Checked directly on this page's own
data: the three strips built during the demo hold 5, 5, and 5 points, but the bounded inner loop
only runs 3, 4, and 4 comparisons — not the 10 a full pairwise check of each 5-point strip would
need.
function closestPair(points) {
if (points.length < 2) return null; // no pair to find, see Pitfalls
const byX = [...points].sort((a, b) => a.x - b.x);
function dist(a, b) { return Math.hypot(a.x - b.x, a.y - b.y); }
function bruteForce(pts) {
let best = Infinity, pair = null;
for (let i = 0; i < pts.length; i++) {
for (let j = i + 1; j < pts.length; j++) {
const d = dist(pts[i], pts[j]);
if (d < best) { best = d; pair = [pts[i], pts[j]]; }
}
}
return { pair, d: best };
}
function rec(pts) {
if (pts.length <= 3) return bruteForce(pts); // base case: direct comparison
const mid = pts.length >> 1;
const midX = pts[mid].x;
const left = rec(pts.slice(0, mid));
const right = rec(pts.slice(mid));
let best = left.d <= right.d ? left : right;
// Only points within `best.d` of the split line can possibly beat it.
const strip = pts
.filter(p => Math.abs(p.x - midX) < best.d)
.sort((a, b) => a.y - b.y); // real O(n log n) merges this from the two halves instead — see Complexity
for (let i = 0; i < strip.length; i++) {
for (let j = i + 1; j < strip.length && (strip[j].y - strip[i].y) < best.d; j++) {
const d = dist(strip[i], strip[j]);
if (d < best.d) best = { pair: [strip[i], strip[j]], d };
}
}
return best;
}
return rec(byX);
}Skipping the strip check entirely still terminates and still looks plausible — it's just wrong. Checked directly on this page's own point set: a version that returns whichever half's result has the smaller distance, without ever building or checking the strip, reports E-F (d=94.02) as the closest pair. The real answer is F-G (d=10.00) — F is the last point in the left half, G is the first point in the right half, and they're by far the two nearest points in the whole set, but no all-within-one-half comparison ever looks at both of them together. The bug doesn't crash or produce an obviously malformed result; it just confidently returns the wrong pair, which is exactly why the strip step can't be treated as an optional refinement.
Coincident points are a legitimate answer, not a special case. Two points at the
exact same coordinates are zero distance apart — the closest possible pair — and nothing about the
algorithm above needs to special-case that: dist returns 0 like any other value, and
0 wins every < comparison it's involved in. Confirmed across the same 20,000-trial
random stress test used to verify the algorithm generally (small coordinate ranges make duplicate
points common): every run with a duplicate pair correctly returned it as the answer.
Fewer than two points has no pair to find at all. The reference implementation's
early return handles this explicitly — an empty array or a single point has nothing to compare
against. Without that guard, bruteForce on a one-point (or zero-point) array runs its
loops zero times and silently returns { pair: null, d: Infinity }, which then
propagates all the way up through every combine step without ever throwing: the bug
would only surface later, wherever the caller assumes pair is never null.
Time: the recursion has the identical shape to
Merge Sort's: split in half, recurse on each half, then a
combine step that touches every element once — T(n) = 2T(n/2) + O(n), which resolves to
O(n log n) by the same master-theorem argument merge sort's own Complexity section
already makes. But that O(n) combine step depends on the strip already being sorted by
y as a byproduct of the recursion — merged up from two already-y-sorted
halves the way merge sort merges its own two sorted halves — not sorted fresh at every level. This
demo, like Huffman Coding's priority queue and
Kruskal's algorithm's edge list, re-sorts the strip by
y from scratch at every level of the recursion for clarity, which costs
O(k log k) per level for a strip of size k and degrades the overall bound
to O(n log² n). A real O(n log n) implementation carries the
y-sorted order up through the recursion as an extra return value instead of re-deriving
it. Measured directly on this page's own 12 points: 66 pairwise comparisons for brute force, versus
12 base-case comparisons plus 11 strip comparisons — 23 total — for the divide-and-conquer version.
Space: O(n) for the recursion's own slices and the strip array at
each level.
This site's guide, Choosing a Geometry Algorithm, places this entry apart from the triangulation/duality trio above — it shares the same bare-point-set starting shape, but asks a genuinely different question (nearest pair, not triangulation or partitioning).