Smallest-circle problem

The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, smallest enclosing 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.[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:

Run of Megiddo's algorithm phase, discarding from point set A, B, ..., U needless points E, T.

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. The solution of the subproblem is either the solution of the unconstrained problem or it is used to determine the half-plane where the unconstrained solution center is located.

The half-plane where the unconstrained solution lies could be determined by the points Pi on the boundary of the constrained circle solution. (The first and last point on the circle in each half-plane suffice. If the center belongs to their convex hull, it is unconstrained solution, otherwise the direction to the nearest edge determines the half-plane of the unconstrained solution.)

Otherwise, point p must lie on the boundary of the result circle. It recurses, but with the set R of points known to be on the boundary as an additional parameter.

The recursion terminates when P is empty, and a solution can be found from the points in R: for 0 or 1 points the solution is trivial, for 2 points the minimal circle has its center at the midpoint between the two points, and for 3 points the circle is the circumcircle of the triangle described by the points. (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 weighted version of the minimum covering circle problem takes as input a set of points in a Euclidean space, each with weights; the goal is to find a single point that minimizes the maximum weighted distance to any point. The original minimum covering circle problem can be recovered by setting all weights to the same number. 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.[15][18][19]