Smallest Enclosing Circle — Welzl's Algorithm

Welzl's algorithm

// welzl(P, R): P = points to consider, R = points on boundary
if (P.isEmpty() || R.size() == 3) return circleFrom(R);
Point p = P.random();
Circle c = welzl(P - {p}, R);
if (c.contains(p)) return c;
return welzl(P - {p}, R + {p});

Complexity

Expected O(N). Move-to-front trick or random shuffle upfront ensures amortized bound.

Boundary support

Enclosing circle uniquely determined by 2 or 3 boundary points. Boundary set R grows monotonically at recursion depth.

Extension to higher dimensions

Smallest enclosing ball in R^d. Welzl generalizes but complexity depends on d.