How to Learn Welzl’s Algorithm: Smallest Enclosing Circles, Support Sets, Randomized Incremental Geometry and Expected Linear Time

Wait, What?

Thousands of points can be enclosed by one smallest circle, yet only two or three boundary points are needed to define the answer.

Welzl’s randomized incremental algorithm solves the smallest enclosing circle problem in expected linear time. Given points in the plane, it finds the unique minimum-radius circle containing them all. Its power comes from a compact geometric invariant: at any stage, the current minimum circle is determined by a tiny support set—at most three boundary points in 2D.

Quick Answer

Learn Welzl through circle geometry → containment → support points → incremental insertion → violated constraints → boundary recursion → randomization → backward analysis → numerical robustness → higher-dimensional generalization. The key insight is that a point matters only when it lies outside the circle built from earlier constraints.

1. Understand the Optimization Problem

Given a finite set P of planar points, find the circle of minimum radius that contains every point in P. The solution is unique. In nondegenerate cases, the optimal circle is determined either by two points forming a diameter or by three points whose circumcircle contains all remaining points.

This immediately suggests a useful learning question: which points are merely passengers inside the final circle, and which points actually constrain the optimum?

2. Learn the Base Cases First

• No support points: the circle is empty.
• One support point: radius zero at that point.
• Two support points: the minimum circle has the segment between them as a diameter.
• Three non-collinear support points: use their circumcircle.

Three collinear points do not define a finite circumcircle in the usual formula; the minimum circle for them is determined by the farthest pair.

3. The Incremental Idea

Suppose a circle already encloses the first k points. Insert the next point p. If p lies inside or on the circle, nothing changes. If p lies outside, the old circle cannot remain optimal because the new answer must include p. Therefore p must become part of the boundary support of the new minimum circle.

This violation-to-boundary step is the heart of Welzl’s recursion.

4. The Recursive Contract

welzl(P, R):
    if P is empty or |R| = 3:
        return minimum_circle_defined_by(R)

    choose and remove a point p from P
    D = welzl(P, R)

    if p is inside D:
        return D
    else:
        return welzl(P, R union {p})

R is the support set that must lie on the boundary of the solution. The algorithm becomes efficient when P is processed in randomized order.

5. Why Randomization Matters

A hostile input order can repeatedly force expensive recomputation. Random shuffling makes it unlikely that many late points become new boundary constraints. Welzl’s backward analysis shows expected linear running time in fixed dimension.

Current CGAL documentation still warns that efficiency depends on input order and explicitly supports randomization for minimum-circle construction.

6. Work a Five-Point Example

Place four points near the corners of a square and one point near the centre. Shuffle the points. Trace the current circle after each insertion. The centre point will never define the final support. Eventually two or three extreme points determine the optimum. Repeat with one point moved far outside the square; that point must become a new support constraint.

This trace teaches the distinction between membership and support: every point must be contained, but only a few determine the boundary.

7. Derive the Two-Point Circle

For support points a and b, the minimum enclosing circle has:

center = (a + b) / 2
radius = distance(a, b) / 2

Before tackling the three-point case, verify this geometrically: any smaller radius could not contain both endpoints.

8. Derive the Three-Point Circumcircle

Three non-collinear points define a unique circumcircle. You can compute its centre by intersecting perpendicular bisectors or by a determinant formula. In robust production code, avoid blindly applying formulas when the triangle is nearly collinear; numerical conditioning matters.

9. Expected O(n) Does Not Mean Every Run Is Linear

Welzl’s algorithm is randomized with expected linear complexity for fixed dimension. A particular input order can be worse. This is a useful lesson in randomized analysis: the guarantee is over the random ordering, not over every deterministic execution trace.

10. Numerical Robustness Is Part of the Professional Algorithm

Floating-point code must decide whether a point lies inside, on, or just outside a circle. A naive equality test can make the recursion unstable. Practical strategies include squared-distance comparisons, carefully scaled tolerances, exact predicates where available, and robust geometry libraries.

Current CGAL 6.2 documentation notes that its older Min_circle_2 interface is not specifically tuned for floating-point robustness and points users toward more general bounding-sphere machinery for many cases.

11. Generalization Beyond 2D

The same LP-type structure generalizes to smallest enclosing balls in fixed dimension. In d dimensions, at most d+1 support points are needed. The algorithmic pattern—randomized incremental processing plus a tiny active constraint set—is more important than the circle itself.

12. Applications

• bounding volumes for collision culling;
• facility-location style geometric summaries;
• minimum-radius coverage problems;
• shape descriptors;
• computer graphics and spatial preprocessing;
• initial bounds inside more complex geometric optimization.

13. How to Learn It Efficiently

Use Predict–Run–Investigate–Modify–Make. Predict which points will support a hand-drawn minimum circle. Run a brute-force reference on small sets. Investigate every point that causes the current circle to change. Modify the insertion order and observe how recursion cost changes. Then make the randomized recursive solver yourself.

A faded worked example is especially effective here: first supply the support-set recursion completely, then remove the containment test, then remove the base-case constructor, and finally ask for the full algorithm.

Common Failure States

• Assuming the arithmetic mean of all points is the optimal centre.
• Confusing a bounding box centre with a minimum enclosing circle centre.
• Forgetting that two support points may define the optimum.
• Applying a circumcircle formula to nearly collinear triples without safeguards.
• Not randomizing input and then treating poor deterministic behaviour as the algorithm’s expected complexity.
• Using an arbitrary epsilon that scales badly with coordinate magnitude.
• Returning a circle defined by support points without verifying that all points are contained.

Practice Ladder

• Beginner: identify support points in hand-drawn point sets.
• Foundation: implement minimum circles for zero, one, two and three support points.
• Intermediate: implement randomized Welzl recursion and test against brute force.
• Advanced: design robust containment predicates for large and nearly collinear coordinates.
• Professional: compare a custom implementation with CGAL or another robust geometry library across random, adversarial, duplicate and degenerate inputs.

Learning Hall Boundary

This article owns Welzl’s randomized smallest-enclosing-circle algorithm and its support-set reasoning. It does not replace the existing convex-hull, Voronoi, Delaunay, collision-detection or general bounding-volume topics.

Evidence Boundary

Emo Welzl’s 1991 work “Smallest enclosing disks (balls and ellipsoids)” develops the randomized expected-linear-time approach. Current CGAL 6.2 bounding-volume documentation describes minimum enclosing circles/spheres, support sets, randomization and robustness considerations.

Professional rule: you understand Welzl when you can explain why an outside point becomes a boundary constraint, why at most three support points are needed in 2D, and why random order changes expected cost without changing the geometric answer.