Smallest Enclosing Circle

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.

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">{{hint}}</p>
<canvas id="cv" width="440" height="300"></canvas>
<div class="status" id="status">{{click_first}}</div>
<div class="btns">
  <button id="random" type="button">{{btn_random}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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(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)$ 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.

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

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.