The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. The corresponding problem in n-dimensional space, the smallest bounding sphere problem, is to compute the smallest n-sphere that contains all of a given set of points. The smallest-circle problem was initially proposed by the English mathematician James Joseph Sylvester in 1857. The smallest-circle problem in the plane is an example of a facility location problem (the 1-center problem) in which the location of a new facility must be chosen to provide service to a number of customers, minimizing the farthest distance that any customer must travel to reach the new facility. Both the smallest circle problem in the plane, and the smallest bounding sphere problem in any higher-dimensional space of bounded dimension are solvable in worst-case linear time.
Characterization Most of the geometric approaches for the problem look for points that lie on the boundary of the minimum circle and are based on the following simple facts:
The minimum covering circle is unique. The minimum covering circle of a set S can be determined by at most three points in S which lie on the boundary of the circle. If it is determined by only two points, then the line segment joining those two points must be a diameter of the minimum circle. If it is determined by three points, then the triangle consisting of those three points is not obtuse.
Linear-time solutions As Nimrod Megiddo showed, the minimum enclosing circle can be found in linear time, and the same linear time bound also applies to the smallest enclosing sphere in Euclidean spaces of any constant dimension. His article also gives a brief overview of earlier O ( n 3 ) {\displaystyle O(n^{3})} and O ( n log n ) {\displaystyle O(n\log n)} algorithms; in doing so, Megiddo demonstrated that Shamos and Hoey's conjecture – that a solution to the smallest-circle problem was computable in Ω ( n log n ) {\displaystyle \Omega (n\log n)} at best – was false. Emo Welzl proposed a simple randomized algorithm for the minimum covering circle problem that runs in expected time O ( n ) {\displaystyle O(n)} , based on a linear programming algorithm of Raimund Seidel. Subsequently, the smallest-circle problem was included in a general class of LP-type problems that can be solved by algorithms like Welzl's based on linear programming. As a consequence of membership in this class, it was shown that the dependence on the dimension of the constant factor in the O ( n ) {\displaystyle O(n)} time bound, which was factorial for Seidel's method, could be reduced to subexponential. Welzl's minidisk algorithm has been extended to handle Bregman divergences which include the squared Euclidean distance.
Megiddo's algorithm
… excerpt ends here. Continue reading the full article.
