The twelfth Geometry entry, and the first whose answer is a shape sized to fit the whole input rather than a fact about one point, one pair, or one polygon's interior. Given a set of points, what's the smallest circle that contains every one of them? Every support point of that circle — every point actually touching its boundary — is provably a vertex of the point set's convex hull (confirmed directly: 0 violations across 3,000 random trials of 5–19 points), so this is a genuinely different question from the ones the rest of this category answers, but a related one to Closest Pair of Points's "bare point set, no boundary" starting shape. The obvious-looking shortcut — find the two farthest-apart points and draw a circle with them as the diameter — is wrong far more often than it's right, which is most of what this page is actually about.
Eight points, three of them (A, B, C) placed in a near-equilateral triangle, the rest scattered safely inside it. Press Step or Run to watch the algorithm process points one at a time in the order chosen below, growing a working circle only when the next point falls outside it. The order selector processes the identical eight points and produces the identical final circle either way — only the amount of internal work changes. The checkbox overlays the "just use the two farthest points" shortcut for comparison.
This is Welzl's randomized incremental construction, in the common "move-to-front" iterative
form: process the points one at a time in a fixed order, keeping a working circle that's always the
smallest circle enclosing every point seen so far. A new point that's already inside the
working circle changes nothing. A point outside it can't be — the working circle was already
minimal for the smaller set, and any circle enclosing the new set has to enclose this point too, so
the boundary must move to reach it, and the new point must be on the boundary of
whatever circle replaces it. That's the whole recursive structure: rebuild from scratch with this
point pinned to the boundary, re-scanning every earlier point against the new candidate exactly the
same way, one dimension down each time it happens again (a two-point diameter circle, tested against
even-earlier points; a three-point circumcircle, which needs no further test at all — three points
not all on one line pin a circle uniquely, so there is nothing left to violate). Three points is the
recursion's floor because a circle in the plane has exactly three degrees of freedom (center
x, center y, radius) — the same reason Delaunay Triangulation's circumcircles are
determined by exactly three points and no fewer.
The expected linear running time comes from a backward analysis — the same
proof technique Trapezoidal Map's own Why It Works
section uses for its expected O(n log n) preprocessing bound, applied here to a flat
sum instead of a harmonic one. Fix any prefix of i points already processed in random
order, and ask: how likely is it that the i-th point was actually essential — one of
the (at most three) points supporting the circle for that prefix? Since the order is uniformly
random, any of the i points is equally likely to have landed last, and at most three of
them are ever support points, so that probability is at most 3/i. When the
i-th point is essential, the rebuild it triggers costs at most
O(i) work (rescanning every earlier point). Multiply and sum:
Σ O(i) · (3/i) = Σ O(3) = O(n) over all n points — a flat sum, not
log n, precisely because the "cost when it happens" and the "chance it happens" cancel
each other's dependence on i exactly, instead of just shrinking together. The bound is
on the expectation, not any single run — see Pitfalls for what a non-random order actually
does to it.
function circleFrom1(a) { return { x: a.x, y: a.y, r: 0 }; }
function circleFrom2(a, b) {
return { x: (a.x + b.x) / 2, y: (a.y + b.y) / 2, r: Math.hypot(a.x - b.x, a.y - b.y) / 2 };
}
function circleFrom3(a, b, c) {
const d = 2 * (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
if (Math.abs(d) < 1e-9) { // collinear: no unique circumcircle, fall back
return [circleFrom2(a, b), circleFrom2(a, c), circleFrom2(b, c)]
.reduce((best, cc) => (cc.r > best.r ? cc : best));
}
const a2 = a.x * a.x + a.y * a.y, b2 = b.x * b.x + b.y * b.y, c2 = c.x * c.x + c.y * c.y;
const x = (a2 * (b.y - c.y) + b2 * (c.y - a.y) + c2 * (a.y - b.y)) / d;
const y = (a2 * (c.x - b.x) + b2 * (a.x - c.x) + c2 * (b.x - a.x)) / d;
return { x, y, r: Math.hypot(x - a.x, y - a.y) };
}
const EPS = 1e-7;
function inside(c, p) {
const dx = c.x - p.x, dy = c.y - p.y;
return dx * dx + dy * dy <= (c.r + EPS) * (c.r + EPS);
}
function smallestEnclosingCircle(points) {
shuffle(points); // load-bearing — see Pitfalls
let circle = null;
for (let i = 0; i < points.length; i++) {
const p = points[i];
if (circle && inside(circle, p)) continue;
circle = circleFrom1(p);
for (let j = 0; j < i; j++) {
if (inside(circle, points[j])) continue;
circle = circleFrom2(p, points[j]);
for (let k = 0; k < j; k++) {
if (inside(circle, points[k])) continue;
circle = circleFrom3(p, points[j], points[k]);
}
}
}
return circle;
}Skipping the shuffle doesn't break correctness — the algorithm above still reaches the
exact right circle no matter what order it's fed. It breaks the only reason to use this algorithm
over a simpler one: the expected-linear time bound. The backward analysis above depends on
every prefix being a uniformly random sample, which a fixed, structured order isn't. Feeding the
identical eight demo points above in an order where the three true boundary points (A, B, C) arrive
last instead of first costs 59 inside-checks to reach the same circle that
arriving-first reaches in 12 — a 4.9× difference on the same 8 points, purely
from order, reproducible directly in the demo above. The effect gets far more dramatic at scale:
sweeping points already sorted by angle around a common circle (the worst realistic case — no
shuffle ever gets applied) against the identical points in random order, both measured by counting
real inside() calls:
| n | angle-sorted order | random order (avg of 20 shuffles) | ratio |
|---|---|---|---|
| 100 | 1,742 | 472.7 | 3.7× |
| 200 | 6,643 | 750.3 | 8.9× |
| 400 | 24,813 | 1,657.2 | 15.0× |
| 800 | 95,588 | 3,091.6 | 30.9× |
| 1,600 | 361,391 | 8,030.6 | 45.0× |
The angle-sorted column roughly quadruples with every doubling of n — the real
signature of O(n²) growth, the outcome the backward analysis explicitly doesn't cover
once the order stops being random. The random column stays close to linear. The shuffle isn't a
defensive nicety; it's the one line of code the entire complexity bound rests on.
"Find the two farthest-apart points and draw a circle with them as the diameter" looks
like the answer, uses the same points this algorithm would call a support set, and is simply wrong
whenever the true answer needs all three. On a clean equilateral triangle with side
10, the real smallest enclosing circle has radius 5.7735 (the circumcircle, all three
vertices on the boundary); the farthest-pair shortcut reports 5.0000 (any two vertices
are equally far apart, so it picks a pair arbitrarily) — a circle that misses the third vertex by
8.6603 − 5.0000 = 3.6603 units, over 70% of its own radius. This isn't a rare
near-miss: across 20,000 random triangles, the farthest-pair shortcut fails to enclose all three
points 27.7% of the time — any triangle with no obtuse angle needs all three
vertices, and only an obtuse (or right) triangle lets the longest side's two endpoints suffice as a
diameter. The same failure shows up on the demo's own 8-point set: the farthest pair is
B–C (checkable directly with the comparison checkbox above),
giving a circle of radius 150 that misses A by 80 units and both
E and H by roughly 11 — three separate points outside a circle
that's supposed to contain everything, not a boundary-hugging rounding error.
Time: O(n) expected, via the backward analysis above — genuinely
linear, not n log n, because a circle's support set is bounded by a constant (3) rather
than growing with the input the way a convex hull's does. Worst case (adversarial or unshuffled
order) degrades toward O(n²), exactly the growth pattern measured in Pitfalls.
Space: O(1) beyond the input itself — only the current circle and its
at-most-three support points are ever held at once, no matter how many points have already been
processed. Verified against an O(n⁴) brute-force oracle (every candidate circle from
all pairs and all triples of points, keeping the smallest one that encloses everything) across 5,000
random trials at 2–8 points: 0 mismatches, radii agreeing to within 7 ×
10⁻¹⁵ of each other, plus degenerate cases checked directly — collinear points, duplicate
points, all-identical points, a single point, and exactly two points all produce the correct circle.
This site's guide, Choosing a Geometry Algorithm, places this entry as a fourth, genuinely different question from the other eleven: not "is this point inside," not "do these cross," not "triangulate or partition this region," but "what's the smallest shape that fits around everything at once."