Smallest-circle problem
The smallest-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 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.
Since is minimal, we must have, meaning, so the disks are identical.
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 and O algorithms.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.
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.
Megiddo's algorithm
Megiddo's algorithm is based on the technique called prune and search reducing size of the problem by removal of n/16 of unnecessary points.That leads to the recurrence t≤ t+cn giving t=16cn.
The algorithm is rather complicated and it is reflected in big multiplicative constant.
The reduction needs to solve twice the similar problem where center of the sought-after enclosing circle is constrained to lie on a given line.
The solution of the subproblem is either solution of unconstrained problem or it is used to determine the half-plane where the unconstrained solution center is located.
The n/16 points to be discarded are found the following way:
Points are arranged to pairs what defines n/2 lines as their bisectors.
Median of bisectors in order by their directions is found and pairs from bisectors are made, such that in each pair one bisector has direction at most and the other at least
Let be intersection of bisectors of -th pair.
Line in the direction is placed to go through an intersection such that there is n/8 intersections in each half-plane defined by the line.
Constrained version of the enclosing problem is run on line what determines half-plane where the center is located.
Line in the direction is placed to go through an intersection such that there is n/16 intersections in each half of the half-plane not containing the solution.
Constrained version of the enclosing problem is run on line what together with determines quadrant, where the center is located.
We consider the points in the quadrant not contained in a half-plane containing solution.
One of the bisectors of pair defining has the direction ensuring which of points defining the bisector is closer to each point in the quadrant containing the center of the enclosing circle. This point could be discarded.
The constrained version of the algorithm is also solved by the prune and search technique, but reducing problem size by removal of n/4 points
leading to recurrence t≤ t+cn giving t=4cn.
The n/4 points to be discarded are found the following way:
Points are arranged to pairs.
For each pair intersection of its bisector with the constraining line is found.
.
Median of points on the line is found and in O time is determined which halfline of starting in
contains the solution of the constrained problem.
We consider points from the other half.
We know which of points defining is closer to the each point of the halfline containing center of the enclosing circle
of the constrained problem solution. This point could be discarded.
The half-plane where the unconstrained solution lies could be determined by
the points on the boundary of the constrained circle solution.
Welzl's algorithm
Welzl described the algorithm in a recursive form.For size of input set at most 3, trivial algorithm is created. It outputs empty circle, circle with radius 0, circle on diameter made by arc of input points for input sizes 0, 1 and 2 respectively.
For input size 3 if the points are vertices of an acute triangle, the circumscribed circle is returned. Otherwise the circle having a diameter of the triangle's longest edge is returned.
For bigger sizes the algorithm uses solution of 1 smaller size where the ignored point is chosen randomly and uniformly.
The returned circle is checked and if it encloses, it is returned as result.
Otherwise we know point is on border of the result. We rerun the algorithm again, but we call it with the information is on the result circle boundary.
Points which are known to be on the boundary are accumulated in the set and they are excluded from the subset from which random choices are made in the following calls.
The condition to use the trivial algorithm is ||=0 or ||=3, and the trivial algorithm is called for.
Equivalent condition would be ||=3 or ||+||≤3, and call of the trivial algorithm for in the case ||=3
and for union of and otherwise.
This would prevent some recursive calls on bottom of the recursion.
algorithm welzl is
input: Finite sets and of points in the plane ||≤ 3.
output: Minimal disk enclosing with on the boundary.
if is empty or || = 3 then
return trivial
choose in
D := welzl
if is in then
return
return welzl
Welzl indicated implementation without need of recursion.
Empty and random permutation of is used at start.
Sets on bottom of recursion correspond to prefixes in the permutation.
Trivial algorithm is called for extended by prefix of to size of 3,
and following points are checked they are enclosed by its result.
Whenever check fails on point, is added to and removed from,
and the prefix of the permutation up to is reshufled.
To make this implementation equivalent to the recursive one, we should maintain stack of prefix lengths and if
longer prefix than the top would be inserted, last point from should be removed and inserted to, the top prefix on the stack should be removed at the same time. Therefore, the prefix length on stack would be nondecreasing from its top down.
When ||=3, the points up to prefix length on top position of the stack are not checked.
Typical implementation uses one list of points of ∪ with in its start, remembering the size of, therefore could be used as stack pointer and its decrements while top prefix length was smaller than the current prefix length to be inserted does all required actions.
Welzl also proposes functionally different version of the algorithm using random permutation of points on input,
where the points are not reshuffled when the point is moved to front of the list.
The algorithm is again presented in the recursive form.
Matoušek, Sharir, Welzl's algorithm
Matoušek, Sharir, Welzl implicitly warned that the assumption point moved to remains on enclosing circle's boundary for all subsets of∪ does not hold, and the required additional condition is the radius of the enclosing circle does not decrease.
They proposed tiny change to the algorithm forcing the radius of the enclosing circle does not decrease.
If is not in enclosing circle of ∪ -,
the radius of enclosing circle of must be smaller than radius of enclosing circle of ∪.
But radius of an enclosing circle of any subset of ∪ - is at most,
so whenever > is radius of an enclosing circle of a subset of ∪, must be in its boundary.
MSW algorithm chooses 3 random points of as initial base and they find initial
by running the trivial algorithm on them.
The presented recursive version of the algorithm is very similar to Welzl's.
Point of is chosen in random order and algorithm for the set - is called.
If is not enclosed by returned circle, replaces one of 3 points in the base
,
such that the enclosing circle of the new base encloses the point removed from the base.
The result recursion is restarted with changed,.
algorithm msw is
input: Finite sets and of points in the plane ||=3
output: Minimal disk enclosing ∪
if is empty then
return trivial
choose in
D := msw
if is in then
return
:= nonbase
return msw
Use of base extended by one point is mentioned in the paper.
If we put to the extended base replacing extension,
we could use Welzl's recurrence to rearrange the extended base to base and the extra point.
You can look at it as allowing temporary decrease of radius which would be restored when the extended base is finished.
The move to front version of Welzl's algorithm works according to this schema except the randomization of choices.
This is why it returns correct results, on the contrary to the Welzl's original algorithm.
Move to front version of welzl without recursion and one list for ∪ in view of msw algorithm
could be simplified by not maintaining the size of at all.
Experiments indicate the move to front version have performance slightly better
than the rerandomized one.
Other algorithms
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 by testing the circles determined by all pairs and triples of points.- An algorithm of Chrystal and Peirce applies a local optimization strategy that maintains two points on the boundary of an enclosing circle and repeatedly shrinks the circle, replacing the pair of boundary points, until an optimal circle is found. Chakraborty and Chaudhuri propose a linear-time method for selecting a suitable initial circle and a pair of boundary points on that circle. Each step of the algorithm includes as one of the two boundary points a new vertex of the convex hull, so if the hull has h vertices this method can be implemented to run in time O.
- Elzinga and Hearn described an algorithm which maintains a covering circle for a subset of the points. At each step, a point not covered by the current sphere is used to find a larger sphere that covers a new subset of points, including the point found. Although its worst case running time is O, the authors report that it ran in linear time in their experiments. The complexity of the method has been analyzed by Drezner and Shelah. Both Fortran and C codes are available from.
- The smallest sphere problem can be formulated as a quadratic program defined by a system of linear constraints with a convex quadratic objective function. Therefore, any feasible direction algorithm can give the solution of the problem. Hearn and Vijay proved that the feasible direction approach chosen by Jacobsen is equivalent to the Chrystal–Peirce algorithm.
- The dual to this quadratic program may also be formulated explicitly; an algorithm of Lawson can be described in this way as a primal dual algorithm.
- Shamos and Hoey proposed an O time algorithm for the problem based on the observation that the center of the smallest enclosing circle must be a vertex of the farthest-point Voronoi diagram of the input point set.
Weighted variants of the problem