Details

The smallest circle problem is also known as the minimum covering circle problem, bounding circle problem or smallest enclosing circle problem. For points, a naive solution runs in time, but this randomized algorithm runs in expected linear time, using the MSW algorithm [1]. This recursive algorithm builds and corrects the bounding circle. It returns the minimum circle , with circle center and the radius . See the initialization code for implementations of the functions msw, trivialMinCircle and nonbase.

msw algorithm: input: finite sets and of points in the plane, output: minimal disk enclosing if is empty return trivialMinCircle() choose (randomly and uniformly) if : return

Reference

[1] J. Matsuoka, M. Sharir and E. Welzl, "A Subexponential Bound for Linear Programming," Algorithmica, 16(4–5), 1996 pp. 498–516. doi:10.1007/BF01940877.