# The circle with minimal radius covering known finite set of points on a plane

Given some points on a plane, how to determine the circle with minimal radius covering all these points?

• It can be solved in linear time via Linear Programming: Megiddo, Nimrod (1983), "Linear-time algorithms for linear programming in $\mathbb{R}^3$ and related problems", SIAM Journal on Computing 12 (4): 759–776. – Joseph O'Rourke Jul 10 '15 at 18:57

## 1 Answer

Although I quoted Meggido's 32-yr-old LP algorithm in the comments, a simpler-to-implement randomized algorithm has expected linear time and space complexity, and is the most common implementation, e.g., as cited below the figure.

(Image from code.project.com.)
A clear description of this algorithm may be found in this lecture prepared by Marc van Kreveld and Maarten Loffler: PDF slides download.

CGAL implements both a heuristic algorithm, and the LP algorithm, in $\mathbb{R}^d$: CGAL implementation.