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

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.

Why it is $O(n)$ — backwards analysis

After processing $i$ points, the circle is determined by at most 3 of them. Since the order was random, the probability that the $i$-th point is one of those 3 is $3/i$. So the expected work at level $i$ is $\frac{3}{i}\cdot O(i)=O(1)$, and the total is $O(n)$.

The same argument at each nesting level keeps the whole thing linear. This is backwards analysis, the same technique that analyses Seidel’s LP and randomised incremental Delaunay.

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 time-seeded RNG so the order cannot be predicted.

Circumcentre

PD circumcenter(PD a, PD b, PD c) {
    PD ba = b - a, ca = c - a;
    double d = 2 * cross(ba, ca);
    double x = (ca.y * norm2(ba) - ba.y * norm2(ca)) / d;
    double y = (ba.x * norm2(ca) - ca.x * norm2(ba)) / d;
    return a + PD{x, y};
}

Degenerate when the three points are collinear ($d=0$) — in that case the enclosing circle is determined by the two extreme points, which the algorithm’s structure already handles.

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

Variants

Variant	Method
Minimum enclosing rectangle	rotating calipers on the hull (Toussaint)
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
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, which is a different and harder problem with no exact algorithm.

Preprocessing with the hull

Only points on the convex hull can determine the circle, 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.

See also: Welzl’s Algorithm · Seidel’s LP · Convex Hull