Minimum Enclosing Circle

Welzl's randomized incremental algorithm — the circle adjusts as boundary points are found

Welzl: expected O(n) Brute force: O(n³) Determined by 2 or 3 points LP-type, dim 3
Slow Fast
Step: 0/0  |  Inside tests: 0  |  Rebuilds: 0  |  Radius: —
point inside
point OUTSIDE (triggers rebuild)
boundary / support point
current circle

What's happening

Press Run to watch Welzl process points one at a time, or Step to advance manually. The circle only rebuilds when a point falls outside.

Complexity

ApproachTimeSpace
Inside testO(1)O(1)
Circle from 2 ptsO(1)O(1)
Circumcircle (3 pts)O(1)O(1)
Welzl (this anim)exp. O(n)O(n)
Brute forceO(n³)–O(n⁴)O(1)
Megiddo (det.)O(n)O(n)

Operation log