Given some points on a plane, how to determine the circle with minimal radius covering all these points?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ 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. $\endgroup$– Joseph O'RourkeCommented Jul 10, 2015 at 18:57
Add a comment
|
1 Answer
$\begingroup$
(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.
$\endgroup$
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.
answered Jul 10, 2015 at 20:11