Introduction

Scatter a handful of points on a table. Now ask: what is the smallest circle that still contains every one of them? You could be choosing where to build a hospital so that no village is too far, or sizing the lens that must cover a cluster of stars. The question is ancient and the answer is unique — for any set of points there is exactly one smallest enclosing circle.

The surprise is what pins it down. Out of dozens or thousands of points, the smallest circle is decided by at most three of them sitting on its boundary (sometimes just two, at the ends of a diameter). Every other point sits comfortably inside, irrelevant to the answer.

So the real puzzle is not geometry but search: how do you find those two or three special points without testing every combination? In 1991 Emo Welzl gave an answer so clean it feels like a magic trick — and it runs in expected linear time.

Try It

Click inside the box to drop points. After each click the smallest enclosing circle is recomputed and the points that actually define it — the ones touching the boundary — light up. Watch how only two or three points ever matter, no matter how many you add.

<p class="hint">Click inside the box to drop points. The <b>smallest enclosing circle</b> is recomputed after every click, and the at-most-three points that actually define it (the ones touching the boundary) light up.</p>
<canvas id="cv" width="440" height="300"></canvas>
<div class="status" id="status">Click to add your first point.</div>
<div class="btns">
  <button id="random" type="button">Add 5 random</button>
  <button id="reset" type="button" class="ghost">Clear</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 { width: 100%; max-width: 440px; height: auto; background: #f3f6f9;
         border: 1px solid #cdd9e3; border-radius: 10px; cursor: crosshair; display: block; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; color: #1d3557; }
.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] ?? ''));
// Smallest enclosing circle via Welzl's randomized incremental algorithm.
// Expected O(n) time (Welzl, 1991). The circle is always defined by at most
// 3 of the points (the "support" set) lying on its boundary.
const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
let pts = [];

const dist = (a, b) => Math.hypot(a.x - b.x, a.y - b.y);
function circleFrom2(a, b) {
  return { x: (a.x + b.x) / 2, y: (a.y + b.y) / 2, r: dist(a, b) / 2 };
}
function circleFrom3(a, b, c) {
  const ax = a.x, ay = a.y, bx = b.x, by = b.y, cx = c.x, cy = c.y;
  const d = 2 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by));
  if (Math.abs(d) < 1e-9) return null; // collinear
  const ux = ((ax*ax+ay*ay)*(by-cy) + (bx*bx+by*by)*(cy-ay) + (cx*cx+cy*cy)*(ay-by)) / d;
  const uy = ((ax*ax+ay*ay)*(cx-bx) + (bx*bx+by*by)*(ax-cx) + (cx*cx+cy*cy)*(bx-ax)) / d;
  const cen = { x: ux, y: uy };
  return { x: ux, y: uy, r: dist(cen, a) };
}
const inCircle = (c, p) => c && dist(c, p) <= c.r + 1e-7;

// Build the smallest circle whose boundary set R (size <=3) is honored.
function trivial(R) {
  if (R.length === 0) return { x: 0, y: 0, r: 0 };
  if (R.length === 1) return { x: R[0].x, y: R[0].y, r: 0 };
  if (R.length === 2) return circleFrom2(R[0], R[1]);
  // 3 points: the unique circle through them, or fall back to best pair.
  const c = circleFrom3(R[0], R[1], R[2]);
  if (c) return c;
  let best = circleFrom2(R[0], R[1]);
  const c2 = circleFrom2(R[0], R[2]); if (c2.r < best.r) best = c2;
  const c3 = circleFrom2(R[1], R[2]); if (c3.r < best.r) best = c3;
  return best;
}
// Iterative Welzl: incremental with at most 3 boundary points.
function welzl(points) {
  const P = points.slice();
  for (let i = P.length - 1; i > 0; i--) { // shuffle
    const j = Math.floor(Math.random() * (i + 1));
    [P[i], P[j]] = [P[j], P[i]];
  }
  let c = trivial(P.slice(0, Math.min(1, P.length)));
  const support = P.length ? [P[0]] : [];
  let circle = P.length ? { x: P[0].x, y: P[0].y, r: 0 } : { x: 0, y: 0, r: 0 };
  let supp = P.length ? [P[0]] : [];
  for (let i = 1; i < P.length; i++) {
    if (inCircle(circle, P[i])) continue;
    // P[i] must be on the boundary.
    circle = { x: P[i].x, y: P[i].y, r: 0 }; supp = [P[i]];
    for (let j = 0; j < i; j++) {
      if (inCircle(circle, P[j])) continue;
      circle = circleFrom2(P[i], P[j]); supp = [P[i], P[j]];
      for (let k = 0; k < j; k++) {
        if (inCircle(circle, P[k])) continue;
        const c3 = circleFrom3(P[i], P[j], P[k]);
        if (c3) { circle = c3; supp = [P[i], P[j], P[k]]; }
      }
    }
  }
  return { circle, supp };
}

function isSupport(p, supp) { return supp.some(s => Math.abs(s.x - p.x) < 1e-6 && Math.abs(s.y - p.y) < 1e-6); }

function draw() {
  ctx.clearRect(0, 0, cv.width, cv.height);
  let res = { circle: { x: 0, y: 0, r: 0 }, supp: [] };
  if (pts.length >= 1) res = welzl(pts);
  const { circle, supp } = res;
  if (circle.r > 0) {
    ctx.beginPath(); ctx.arc(circle.x, circle.y, circle.r, 0, 7);
    ctx.strokeStyle = '#1d3557'; ctx.lineWidth = 2; ctx.stroke();
    ctx.beginPath(); ctx.arc(circle.x, circle.y, 3, 0, 7);
    ctx.fillStyle = '#1d3557'; ctx.fill();
  }
  for (const p of pts) {
    const on = isSupport(p, supp);
    ctx.beginPath(); ctx.arc(p.x, p.y, on ? 6 : 4, 0, 7);
    ctx.fillStyle = on ? '#e63946' : '#5a7088'; ctx.fill();
  }
  const s = document.getElementById('status');
  if (!pts.length) s.textContent = 'Click to add your first point.';
  else s.textContent = fmt('%length% {{pt_word_%v%}} · circle pinned by %length2% {{bpt_word_%v2%}} · radius %round%', { length: pts.length, v: pts.length>1?'pl':'sg', length2: supp.length, v2: supp.length===1?'sg':'pl', round: Math.round(circle.r) });
}

cv.addEventListener('click', e => {
  const rect = cv.getBoundingClientRect();
  const sx = cv.width / rect.width, sy = cv.height / rect.height;
  pts.push({ x: (e.clientX - rect.left) * sx, y: (e.clientY - rect.top) * sy });
  draw();
});
document.getElementById('random').addEventListener('click', () => {
  for (let i = 0; i < 5; i++)
    pts.push({ x: 30 + Math.random() * (cv.width - 60), y: 30 + Math.random() * (cv.height - 60) });
  draw();
});
document.getElementById('reset').addEventListener('click', () => { pts = []; draw(); });
draw();
Result
Console

Notice the behavior. Most points you add do nothing: they fall inside the current circle and leave it unchanged. Only when a new point lands outside does the circle jump, re-snapping to a fresh set of at most three boundary points. That "usually nothing happens" pattern is exactly why Welzl's randomized version is so fast on average.

The Real Complexity

How hard is it to find the smallest enclosing circle, really?

  • Brute force is tempting: every smallest circle is fixed by 2 or 3 boundary points, so try all pairs and triples, build their circle, and keep the smallest that covers everything. That is O(n4)O(n^{4}) — checking every candidate against every point — correct but slow.
  • A clean linear-program flavor. The problem is LP-type: adding a point either leaves the answer alone or forces it onto the boundary. That structure is what makes a fast incremental method possible.
  • It's solved, optimally. In 1991 Emo Welzl published a randomized incremental algorithm that runs in expected O(n)O(n) time — linear, the best you could hope for since you must at least read every point. It adds points in random order; if a new point is inside the current circle it is ignored, otherwise the circle is rebuilt knowing the new point must lie on its boundary.
  • Why randomness helps. In random order, a new point lands outside only rarely, so the expensive rebuilds are few. The worst case is unlucky, but the average over orderings is provably linear.

So unlike the famously open P vs NP questions, this is a closed case: the smallest enclosing circle is a solved problem with a fast, elegant, provably optimal algorithm.

Where It Matters

"Find the tightest ball around a set of things" turns up far more often than you would guess:

  • Facility placement: put a transmitter, hospital, or warehouse so the farthest customer is as close as possible — that center is exactly the smallest enclosing circle's center (the 1-center problem).
  • Collision detection and graphics: games and simulations wrap objects in bounding circles or spheres so they can reject far-apart pairs instantly before doing expensive exact tests.
  • Clustering and statistics: the minimum enclosing ball summarizes how spread out a group of data points is and anchors some outlier-detection methods.
  • Manufacturing and metrology: checking whether a drilled hole or machined part fits within tolerance is a minimum-circle question.

The same idea generalizes to spheres in higher dimensions, and the closely related closest pair of points shows how a little geometric structure turns a brute-force search into something fast.

Conclusion

The smallest enclosing circle hides a quiet lesson: a problem that looks like it should require weighing every point against every other is really decided by just two or three. Find those, and you are done.

Welzl's trick — add points in random order, only act when one escapes — turns that insight into an algorithm that is short to write, fast in practice, and provably expected-linear. It is a reminder that not every hard-sounding question is hard; sometimes, unlike P vs NP, the answer is already tied up with a neat bow.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/smallest-enclosing-circle/Content licensed under CC BY-NC 4.0.