Smallest circle problem
The smallest-circle problem or minimum covering circle problem is a mathematical 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 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:
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.
Emo Welzl 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. The algorithm is recursive, and takes as arguments two sets of points S and Q; it computes the smallest enclosing circle of the union of S and Q, as long as every point of Q is one of the boundary points of the eventual smallest enclosing circle. Thus, the original smallest enclosing circle problem can be solved by calling the algorithm with S equal to the set of points to be enclosed and Q equal to the empty set; as the algorithm calls itself recursively, it will enlarge the set Q passed into the recursive calls until it includes all the boundary points of the circle.
...
Wikipedia