Smallest-circle problem
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.
[1] The smallest-circle problem was initially proposed by the English mathematician James Joseph Sylvester in 1857.
[2] 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.
[3] 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.
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: Let P be any set of points in the plane, and suppose that there are two smallest enclosing disks of P, with centers at
[4] As Nimrod Megiddo showed,[5] 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.
algorithms;[6] in doing so, Megiddo demonstrated that Shamos and Hoey's conjecture – that a solution to the smallest-circle problem was computable in
[7] Emo Welzl[8] proposed a simple randomized algorithm for the minimum covering circle problem that runs in expected time
, based on a linear programming algorithm of Raimund Seidel.
As a consequence of membership in this class, it was shown that the dependence on the dimension of the constant factor in the
time bound, which was factorial for Seidel's method, could be reduced to subexponential.
[6] Welzl's minidisk algorithm has been extended to handle Bregman divergences[9] which include the squared Euclidean distance.
Megiddo's algorithm[10] is based on the technique called prune and search, reducing the size of the problem by removing
The algorithm is rather complicated and it is reflected by its big multiplicative constant.
The reduction needs to solve twice the similar problem where the center of the sought-after enclosing circle is constrained to lie on a given line.
intersections in each half-plane defined by the line (median position).
The constrained version of the enclosing problem is run on the line q' which determines half-plane where the center is located.
The constrained version of the enclosing problem is run on line q′ which together with q determines the quadrant where the center is located.
One of the bisectors of the pair defining Qk has the direction ensuring which of points Pi defining the bisector is closer to each point in the quadrant containing the center of the enclosing circle.
The constrained version of the algorithm is also solved by the prune and search technique, but reducing the problem size by removal of
The median M of points Qj on the line q is found and in O(n) time is determined which halfline of q starting in M contains the solution of the constrained problem.
It recurses, but with the set R of points known to be on the boundary as an additional parameter.
(In three dimensions, 4 points require the calculation of the circumsphere of a tetrahedron.)
Recursion can also terminate when R has size 3 (in 2D, or 4 in 3D) because the remaining points in P must lie within the circle described by R. Welzl's paper states that it is sufficient to randomly permute the input at the start, rather than performing independently random choices of p on each recursion.
It also states that performance is improved by dynamically re-ordering the points so that those that are found to be outside a circle are subsequently considered earlier, but this requires a change in the structure of the algorithm to store P as a "global".
Prior to Megiddo's result showing that the smallest-circle problem may be solved in linear time, several algorithms of higher complexity appeared in the literature.
A naive algorithm solves the problem in time O(n4) by testing the circles determined by all pairs and triples of points.
The original (unweighted) minimum covering circle problem corresponds to the case when all weights are equal to 1.
As with the unweighted problem, the weighted problem may be solved in linear time in any space of bounded dimension, using approaches closely related to bounded dimension linear programming algorithms, although slower algorithms are again frequent in the literature.
[16][19][20] The smallest enclosing ball of a finite point set has been studied in Riemannian geometry including Cartan-Hadamard manifolds.
