Closest Pair of Points

Scatter a handful of dots on a page and ask: which two are closest together? Your eye answers in an instant. Now scatter ten thousand dots — and suddenly the question is not so trivial.

The obvious recipe is to measure every pair. With n points there are about $n^{2}$/2 pairs, so doubling the points roughly quadruples the work. For a million points that's half a trillion distance checks — too slow for the air-traffic radar, the chip-design tool, or the map app that needs the answer now.

The wonderful surprise is that you don't have to look at every pair. With a clever divide-and-conquer strategy the closest pair falls out in almost-linear time — a textbook example of how the right idea turns a hard-looking problem into an easy one.

Here is a cloud of points. Press Brute force to compare every pair and Divide & conquer to use the smart algorithm. Both highlight the same closest pair in red — but watch the comparison counter.

<p class="hint">{{hint}}</p>
<canvas id="cv" width="320" height="240"></canvas>
<div class="stats">
  <span>{{lbl_points}}: <b id="n">0</b></span>
  <span>{{lbl_comparisons}}: <b id="cmp">—</b></span>
  <span>{{lbl_closest}}: <b id="dist">—</b></span>
</div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="brute" type="button">{{btn_brute}}</button>
  <button id="dc" type="button">{{btn_dc}}</button>
  <button id="add" type="button" class="ghost">{{btn_add}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #f6f9fb;
         display: block; width: 100%; max-width: 320px; touch-action: none; }
.stats { display: flex; gap: 1rem; flex-wrap: wrap; font-size: .9rem; margin: .6rem 0 .2rem; }
.stats b { color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the asymmetry. Checking that a given pair is the closest still means scanning the others, but the two methods of finding it behave completely differently. Brute force grows like $n^{2}$ — add more points and the counter balloons. Divide-and-conquer grows like n log n — add more points and it barely flinches. Press Add 10 points a few times and compare the two counters.

How hard is finding the closest pair, really?

• Brute force compares all pairs: $O(n^{2})$ time. Simple, correct, and hopeless at scale.
• Divide and conquer is $O(n \log n)$. Split the points by a vertical line into a left half and a right half, find the closest pair in each recursively, and let d be the smaller of the two distances. The only pairs left to check straddle the dividing line — and a geometric argument shows that inside the strip of width 2d around the line, each point can have at most a handful of neighbours closer than d. That bounded strip is what kills the quadratic blowup.
• Who and when. This algorithm is due to Michael Shamos and Dan Hoey (1975), one of the founding results of computational geometry.
• It's optimal. In the algebraic decision-tree (comparison) model, finding the closest pair requires Ω(n log n) comparisons, so the Shamos–Hoey algorithm cannot be beaten asymptotically by any comparison-based method.

Unlike the genuinely intractable problems behind P vs NP, closest pair lives firmly in the easy world: it is in P, and we know an algorithm that is provably as fast as possible. The lesson is that "compare everything" is rarely the final word — geometry often hides structure you can exploit.

"Which things are closest?" is a question that shows up everywhere there is space and data:

• Collision avoidance: air-traffic control and robotics constantly ask which two objects are nearest — the pair most at risk of touching.
• Clustering and machine learning: many algorithms (hierarchical clustering, nearest-neighbour methods) repeatedly merge or compare the closest items.
• Geographic systems: placing map labels without overlap, or finding the nearest store, hospital or sensor.
• Graphics and simulation: detecting when particles, characters or molecules are about to overlap.

The divide-and-conquer template here — split, recurse, merge cleverly — is the same engine behind sorting and many other fast algorithms, and it pairs naturally with structures used for pattern matching and spatial search.

The closest pair of points is a small marvel of algorithm design. The brute-force answer is obvious and quadratic; the elegant answer splits the plane, recurses, and merges across a thin strip to reach the provably optimal $O(n \log n)$.

It's a reminder that not every problem that looks like it needs "check everything" actually does. Sometimes the geometry of the situation hands you a shortcut — and unlike the open mysteries surrounding P vs NP, here we know we've found the best possible answer.