Smallest Circle Problem - Linear-time Solutions

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.

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.

The algorithm processes the points of S in a random order, maintaining as it does the set P of processed points and the smallest circle that encloses the union of P and Q. At each step, it tests whether the next point r to be processed belongs to this circle; if it does not, the algorithm replaces the enclosing circle by the result of a recursive call of the algorithm on the sets P and Q+r. Whether the circle was replaced or not, r is then included in the set P. Processing each point, therefore, consists of testing in constant time whether the point belongs to a single circle and possibly performing a recursive call to the algorithm. It can be shown that the ith point to be processed has probability of generating a recursive call, and therefore that the overall time is linear.

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 time bound, which was factorial for Seidel's method, could be reduced to subexponential, while still maintaining only linear dependence on N.