Welzl's Algorithm

Welzl's algorithm computes the smallest circle that encloses every point in a given set of points on a plane, solving what is known as the minimum enclosing circle or smallest-circle problem. It works recursively and randomly: it removes a randomly chosen point from the set, recursively finds the minimum enclosing circle for the remaining points, and only if that smaller circle fails to contain the removed point does it redo the computation with that point fixed on the boundary of the circle being built. This randomized approach gives the algorithm an expected running time that grows only linearly with the number of points, a marked improvement over earlier deterministic approaches to the same problem. Emo Welzl published the algorithm in 1991, and its combination of a simple recursive structure with linear expected time has made it the standard method taught for the minimum enclosing circle problem in computational geometry.