xiv. Minimum Enclosing Circle

Enclosing Circle

The smallest circle containing all $n$ points. Unique, and determined by at most 3 of the points.

The key facts

1. The minimum enclosing circle is unique.
2. It is determined by 2 points (as a diameter) or 3 points (on its boundary).
3. Therefore a brute-force $O(n^4)$ solution exists — but Welzl’s algorithm does it in expected $O(n)$.

Proof: uniqueness and the $\le 3$-point bound

Uniqueness. Suppose two distinct minimum circles $C_1,C_2$ of the same minimal radius $\rho$ both enclose the point set. Their intersection is a lens; consider the circle with diameter equal to the shorter of the two arcs connecting $C_1\cap C_2$‘s two crossing points, specifically: the circle through those two crossing points with the smallest radius that still contains the lens region — concretely, the midpoint circle construction shows that the circle with centre at the midpoint of $C_1,C_2$‘s centres and a carefully chosen smaller radius still covers $C_1\cap C_2\supseteq$ all input points (since every point in a convex lens is covered by a slightly smaller circle centred between the two centres — a standard convexity argument: the intersection of two disks of radius $\rho$ is contained in a disk of radius $<\rho$ centred at the midpoint of the two centres whenever the centres are distinct), contradicting minimality of $\rho$. So $C_1=C_2$.
$\le 3$ points. If the minimum circle has no point on its boundary at all, it can be shrunk — contradiction, so at least one point is on the boundary. If exactly one, it can be shrunk toward that point — contradiction (shrinking slightly towards the single boundary point keeps it inside while reducing the radius, since no other point constrains it), so at least two points are on the boundary whenever the circle cannot be perturbed, UNLESS a single point already forces the radius to $0$ ($n=1$). With exactly two boundary points: if they are not diametrically opposite, the circle can be shrunk and re-centred slightly toward the midpoint of the two points while still covering both and, since no third point is on the boundary to block this, still covering everything else — contradiction — so with exactly two boundary points they must be a diameter. With three or more boundary points, if all three (any three, in fact) do not already pin the circle uniquely (i.e. if a smaller circle through a subset still covers everything), the argument reduces to the two-point or one-point case; otherwise three points already determine the unique circumscribing circle, and a fourth point on the boundary would be a redundant constraint (it must lie on the same circle, since the circle is already fully pinned by three). $■$

Welzl’s algorithm — expected $O(n)$

struct Circle { PD c; double r; };
 
bool inside(const Circle& ci, PD p) { return norm2(p - ci.c) <= ci.r * ci.r + EPS; }
Circle from2(PD a, PD b) { return {(a + b) * 0.5, abs_(a - b) / 2}; }
Circle from3(PD a, PD b, PD c) { PD o = circumcenter(a, b, c); return {o, abs_(o - a)}; }
 
Circle minEnclosingCircle(vector<PD> p) {
    shuffle(p.begin(), p.end(), rng);                 // ESSENTIAL
    Circle c{p[0], 0};
    for (int i = 0; i < (int)p.size(); i++) {
        if (inside(c, p[i])) continue;
        c = {p[i], 0};
        for (int j = 0; j < i; j++) {
            if (inside(c, p[j])) continue;
            c = from2(p[i], p[j]);
            for (int k = 0; k < j; k++) {
                if (inside(c, p[k])) continue;
                c = from3(p[i], p[j], p[k]);
            }
        }
    }
    return c;
}

Three nested loops that look $O(n^3)$ — but the analysis says otherwise. (circumcenter: Triangles; degenerate when the three points are collinear, in which case the enclosing circle is determined by the two extreme points, which the algorithm’s structure already handles since that case is caught by the from2 level before three points are ever fixed together.)

Proof: Welzl's algorithm is correct

Invariant. After processing index $i$, c is the minimum enclosing circle of $p_0,\dots ,p_i$. By induction: if $p_i$ is already inside the circle for $p_0,\dots ,p_{i-1}$, that circle is still minimal and enclosing for $p_0,\dots ,p_i$ too (adding an already-covered point changes nothing). If $p_i$ is outside, it must lie on the boundary of the new minimum circle: if it didn’t, the same circle (minus $p_i$‘s constraint) would still be the minimum enclosing circle for $p_0,\dots ,p_i$, but then it would also enclose $p_0,\dots ,p_{i-1}$ while being a different, and since it must have radius $\ge$ the true minimum for the smaller set, this doesn’t immediately contradict anything — the real argument is simpler: the minimum enclosing circle of $p_0,\dots ,p_i$ has radius $\ge$ that of $p_0,\dots ,p_{i-1}$ (more points, no smaller circle can work), and if $p_i$ were strictly interior to it, removing $p_i$ from the constraint set wouldn’t shrink the circle (it’s still forced by the others) — but $p_i$ outside the old circle while interior to the new one is consistent, so the correct statement is: $p_i$ is outside the circle of the first $i-1$ points, and the new minimum circle (for $i$ points) must be at least that circle’s size; if $p_i$ were in the new circle’s interior, shrinking the new circle slightly toward where it’s “tight” would still have to keep $p_i$ outside (since $p_i$ was outside the smaller, $(i-1)$-point circle, which the new one must enclose) — forcing $p_i$ onto the boundary is exactly the condition that the new minimum circle enclosing all $i+1$ points and touching the constraint imposed by $p_i$ cannot do better than placing $p_i$ exactly on its edge.
The same argument nests: having fixed $p_i$ on the boundary, among $p_0,\dots ,p_{i-1}$ reduce to the sub-problem “smallest circle through $p_i$ enclosing the rest”, and if some $p_j$ ($j<i$) violates the current circle-through-$p_i$, it must also sit on the boundary of the correct circle — by the identical argument one level down. With two points fixed, a circle through both is a one-parameter family (centres along the perpendicular bisector); a third violating point $p_k$ pins it uniquely via from3, and since a circle is determined by at most 3 boundary points (proved above), the recursion never needs a fourth level.

Expected $O(n)$ (backward analysis). The final circle is determined by at most 3 of the $n$ points. For a uniformly random insertion order, by symmetry the probability that the $i$-th point (in the random order) is one of those $\le 3$ “defining” points is at most $3/i$ — so the expected work triggered at step $i$ (an $O(i)$ re-scan when the point is outside the current circle) is $O(i)\cdot \frac{3}{i}=O(1)$. The identical argument applies one nesting level down (fixing one point, the sub-problem over the remaining $i-1$ in their random relative order has the same structure with combinatorial dimension 2) and two levels down (dimension 1), each contributing $O(1)$ expected work per step. Summing $O(1)$ over $i=1,\dots ,n$ at each of the (constant) nesting depths gives $O(n)$ total expected time. $■$

The shuffle is not optional

Without it, an adversarial input (points already sorted so each new one is outside) makes the algorithm $\Theta (n^3)$. Shuffle with a well-seeded RNG so the order cannot be predicted by whoever constructed the test data.

Tested: minEnclosingCircle checked to enclose every input point (within $\epsilon$) and matched in radius against a brute-force $O(n^4)$ search (every pair as a diameter, every triple as a circumscribed circle, keeping the smallest that encloses all points) on random point sets up to $n=12$; also checked on adversarial sorted/collinear inputs to confirm the shuffled version still returns the correct circle (only the unshuffled version would blow up in time, not in correctness, on such inputs).

LP-type problems

Minimum enclosing circle is the archetypal LP-type problem: an optimisation over a set system with bounded combinatorial dimension (3 here), satisfying monotonicity and locality. The same $O(n)$ framework solves:

Problem	Combinatorial dimension
Minimum enclosing circle	3
Minimum enclosing ball in ${\mathbb{R}}^d$	$d+1$
Minimum enclosing ellipse	5
Smallest enclosing annulus	4
Linear programming in dimension $d$	$d$
Distance between two polytopes	$d+1$
Largest ball inside a polytope	$d+1$

Recognising a problem as LP-type tells you immediately that a randomised incremental algorithm is $O(n)$ — see Seidel’s LP for the same framework applied to linear programming, and randomised incremental Delaunay for another application of the same backward-analysis technique.

Variants

Variant	Method
Minimum enclosing rectangle	rotating calipers on the hull (Toussaint) — 07-rotating-calipers
Minimum enclosing square	binary search on the side + a sweep
Smallest circle covering $k$ of $n$ points	much harder; $O(nk)$ or worse
Circle covering all with a fixed radius	is the intersection of the $n$ disks non-empty?
Largest empty circle	a Voronoi vertex, hull edge, or bounding-box constraint — 20-delaunay-and-voronoi
Minimum enclosing ball in 3D	Welzl with dimension 4
Circle minimising the sum of distances	the geometric median — no closed form; use Weiszfeld’s iteration or nested ternary search

The last row is worth flagging: minimising the maximum distance gives the enclosing circle (LP-type, $O(n)$), while minimising the sum gives the geometric median, a different and harder problem with no exact algorithm.

Preprocessing with the hull

Only points on the convex hull can determine the circle (an interior point is never one of the $\le 3$ boundary-defining points, since it’s never extreme in any direction), so taking the hull first reduces $n$ to $h$. Usually not worth it — Welzl is already linear — but useful when the hull is needed anyway.