Introduction

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 n2n^{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.

Try It

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">Each dot is a point. <b>Brute force</b> compares every pair; <b>Divide &amp; conquer</b> uses the smart algorithm. Both find the same closest pair (red) — but watch how many comparisons each one needs.</p>
<canvas id="cv" width="320" height="240"></canvas>
<div class="stats">
  <span>Points: <b id="n">0</b></span>
  <span>Comparisons: <b id="cmp">—</b></span>
  <span>Closest distance: <b id="dist">—</b></span>
</div>
<div class="status" id="status">Add points, then run an algorithm.</div>
<div class="btns">
  <button id="brute" type="button">Brute force</button>
  <button id="dc" type="button">Divide &amp; conquer</button>
  <button id="add" type="button" class="ghost">Add 10 points</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Closest pair of points. Brute force compares all pairs -> O(n^2).
// Divide & conquer sorts by x, recurses on halves, and only checks a thin
// strip around the split line -> O(n log n) (Shamos & Hoey, 1975). Both
// return the SAME closest pair; we count distance comparisons to show the gap.
const cv = document.getElementById('cv'), ctx = cv.getContext('2d');
const W = cv.width, H = cv.height, R = 4;
let pts = [];
const d2 = (a, b) => (a.x - b.x) ** 2 + (a.y - b.y) ** 2;

function seed(k) {
  for (let i = 0; i < k; i++)
    pts.push({ x: 12 + Math.random() * (W - 24), y: 12 + Math.random() * (H - 24) });
}

// ---- Brute force: every pair ----
function brute() {
  let best = Infinity, pair = null, cmp = 0;
  for (let i = 0; i < pts.length; i++)
    for (let j = i + 1; j < pts.length; j++) {
      cmp++;
      const dd = d2(pts[i], pts[j]);
      if (dd < best) { best = dd; pair = [pts[i], pts[j]]; }
    }
  return { best, pair, cmp };
}

// ---- Divide & conquer ----
function dc() {
  const cnt = { v: 0 };
  const px = pts.slice().sort((a, b) => a.x - b.x);
  const r = rec(px, cnt);
  return { best: r.d, pair: r.pair, cmp: cnt.v };
}
function rec(P, cnt) {
  const n = P.length;
  if (n <= 3) {
    let best = Infinity, pair = null;
    for (let i = 0; i < n; i++)
      for (let j = i + 1; j < n; j++) {
        cnt.v++;
        const dd = d2(P[i], P[j]);
        if (dd < best) { best = dd; pair = [P[i], P[j]]; }
      }
    return { d: best, pair };
  }
  const mid = n >> 1, midX = P[mid].x;
  const L = rec(P.slice(0, mid), cnt), Rr = rec(P.slice(mid), cnt);
  let { d, pair } = L.d < Rr.d ? L : Rr;
  // strip of points within sqrt(d) of the dividing line, sorted by y
  const strip = P.filter(p => (p.x - midX) ** 2 < d).sort((a, b) => a.y - b.y);
  for (let i = 0; i < strip.length; i++)
    for (let j = i + 1; j < strip.length && (strip[j].y - strip[i].y) ** 2 < d; j++) {
      cnt.v++;
      const dd = d2(strip[i], strip[j]);
      if (dd < d) { d = dd; pair = [strip[i], strip[j]]; }
    }
  return { d, pair };
}

function draw(pair) {
  ctx.clearRect(0, 0, W, H);
  ctx.fillStyle = '#1d3557';
  for (const p of pts) { ctx.beginPath(); ctx.arc(p.x, p.y, R, 0, 7); ctx.fill(); }
  if (pair) {
    ctx.strokeStyle = '#e63946'; ctx.lineWidth = 2;
    ctx.beginPath(); ctx.moveTo(pair[0].x, pair[0].y); ctx.lineTo(pair[1].x, pair[1].y); ctx.stroke();
    ctx.fillStyle = '#e63946';
    for (const p of pair) { ctx.beginPath(); ctx.arc(p.x, p.y, R + 1.5, 0, 7); ctx.fill(); }
  }
}
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + (cls || ''); }
function refresh(res, label) {
  document.getElementById('n').textContent = pts.length;
  document.getElementById('cmp').textContent = res ? res.cmp : '—';
  document.getElementById('dist').textContent = res && res.pair ? Math.sqrt(res.best).toFixed(1) : '—';
  draw(res ? res.pair : null);
  if (res) setStatus(fmt('%label% found the closest pair in %cmp% comparisons.', { label: label, cmp: res.cmp }), 'ok');
}
function run(fn, label) {
  if (pts.length < 2) { setStatus('Add at least two points first.', ''); return; }
  refresh(fn(), label);
}

document.getElementById('brute').addEventListener('click', () => run(brute, 'Brute force'));
document.getElementById('dc').addEventListener('click', () => run(dc, 'Divide &amp; conquer'));
document.getElementById('add').addEventListener('click', () => { seed(10); refresh(null, ''); setStatus('Added points. Run an algorithm.', ''); });
document.getElementById('reset').addEventListener('click', () => { pts = []; refresh(null, ''); setStatus('Cleared. Add points, then run an algorithm.', ''); });
cv.addEventListener('pointerdown', e => {
  const r = cv.getBoundingClientRect();
  pts.push({ x: (e.clientX - r.left) * W / r.width, y: (e.clientY - r.top) * H / r.height });
  refresh(null, '');
});

seed(20); refresh(null, '');
Result
Console

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 n2n^{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.

The Real Complexity

How hard is finding the closest pair, really?

  • Brute force compares all pairs: O(n2)O(n^{2}) time. Simple, correct, and hopeless at scale.
  • Divide and conquer is O(nlog⁡n)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.

Where It Matters

"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.

Conclusion

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(nlog⁡n)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/closest-pair/Content licensed under CC BY-NC 4.0.