Smallest-circle problem

1. Problem

The minimum covering circle problem is a mathematical problem of computing a smallest enclosing circle of a set S of given N points in Rⁿ, which was initially proposed by Sylvester in 1987 [18]. This problem is also called minimum covering circle problem [4]. In two dimensional space, the problem is a well known single facility location problem which locates a new facility to provide service to a number of customers or facilities [7]. We can formulate the minimum covering circle problem as the minimax programming problem:

$\min _{x\in R^{n}}\max _{x\in S}\|x-s\|$

The problem can be reduced to the following minimization problem:

$\min ~r$

with subject to

$\|x-s\|\leq r$

$x\in R^{n},~s\in S,$

where $r$ can be seen as the radius of the smallest covering circle, or equivalently

$\min ~r$

with subject to

$\|x-s\|+v_{s}=r,$

$v_{s}\geq 0,~x\in R^{n},~s\in S.$

2. Algorithms

From here on we will consider the minimum covering circle problem in two dimensional Euclidean space. 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 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 consists of those three points is not obtuse.

We note that, according to the above facts, the problem can be solved in $O(N^{4})$ by enumerating all the triples of the points in S under a model in which square roots are calculated in constant time.

Chrystal-Peirce Algorithm

The method described in Algorithm 1 first appeared in the papers by Sylvester and Chrystal. In the algorithm, the set $S_{k}$ keeps two points that lie on the boundary of the current circle and the new covering circle is smaller than the previous one. The correctness of the algorithm is based on the facts mentioned earlier. It is not very difficult to see that, in Step 3, the new circle that passes through A, B and C is also a covering circle and smaller than the previous one.

Algorithm 1

Step 1. Set $k=1$. Construct a circle that covers S and passes through two points, say A and B, in S. Find the center of the circle and denote by $O_{k}$.

Step 2. Set $S_{k}=\{A,B\}$. Find a point C that minimizes $\angle ADB$ over $D\in S\setminus S_{k}$. If angle $\angle ADB$ is obtuse, terminate the algorithm and the minimum circle has diameter AB.

Step 3. Set $k=k+1$. Construct the circle that passes through A, B and C, and denote its center by $O_{k}$. If triangle $\vartriangle ABC$ is not obtuse, terminate the algorithm and $O^{\ast }=O_{k}$. Otherwise, $A=C$ if angle $\angle BAC$ is obtuse or $B=C$ if angle $\angle ABC$ is obtuse and go to Step 2.

Suppose that D and E are in S and lie in the other sides of chord AB. Since $\angle ACB\leq \angle ADB$, point D should also be in the new circle. We also know that $\angle ACB+\angle AEB\geq 180^{\circ }$ since they both are covered by the current circle that passes through A and B. This implies that point E is also covered by the new circle that passes through A, B and C.

Chakraborty and Chaudhuri [1] proposes an e±cient selection of initial two points A and B in the first step of the Chrystal-Peirce algorithm which takes $O(N)$. At each iteration of the algorithm, A and B must be extreme points of the convex hull of S. If the number of extreme points is h, then Chrystal-Peirce algorithm runs in $O(hN)$ in the worst case.

Elzinga-Hearn Algorithm

The following method described in Algorithm 2 is due to Elzinga and Hearn [4].

Algorithm 2

Step 1: Select any two points, A and B, in S.

Step 2: Construct a circle with the diameter AB. If the circle covers all the points terminate the algorithm. Otherwise, select a point C which is in outside of the circle.

Step 3: Construct the minimum covering circle for A, B and C. If the circle is defined by two points, then rename those two points by A and B, and go to Step 2.

Step 4: If the current circle defined by A, B and C covers all the points in S, terminate the algorithm. Otherwise, find a point D which is in outside of the current circle.

Step 5: Construct the minimum covering circle for A, B, C and D. If the minimum circle is defined by two points, then go to Step 2. Otherwise, go to Step 4.

Steps 1 and 2 each requires $O(N)$ steps, therefore the worst case running time of the algorithm is $O(h^{3}N)$. However, Elzinga and Hearn [4] reported that computational results showed the algorithm to be O(N) empirically.

Steepest Descent Approach

Mathematical programming formulation of the minimum covering problem is convex. Therefore, any feasible direction algorithm can give the solution of the problem. Jacobsen [9] applied the following feasible direction approach to the problem.

Algorithm 3

Step 1: Set $k=0$. Choose $\epsilon >0$ and select a point $x_{k}$.

Step 2: Solve the problem

$\max _{s\in S}\|x_{k}-s\|.$

Let $s_{i}$ and $r_{i}$ be a solution and the optimal objective function of the above problem, respectively, and let $U_{i}=\{s~|~r_{i}-\|x_{k}-s\|\leq \epsilon \}$.

Step 3: Based on $U_{i}$, determine the set of feasible descent directions from xk. If the set is empty, terminate the algorithm. Otherwise, select a feasible descent direction and calculate the step size in the direction. Denote the new solution $x_{k+1}$ and set $k=k+1$. Go to Step 2.

The optimization problem in Step 2 of Jacobsen's algorithm determines the minimum covering circle of the points in S with the center of $x_{k}$. It is proven that, in this infinite feasible direction method, $x_{k}$ converges to the optimal solution $x^{\ast }$. The feasible descent direction in Step 3 is a cone and Jacobsen selects the bisector of the cone as the descent direction in the implementation. With this selection, Hearn and Vijay [8] proved that the feasible direction approach by Jacobsen is equivalent to the Chrystal-Peirce algorithm.

References

[1] R.K. Chakraborty and P.K. Chaudhuri, Note on Geometrical Solutions for Some Minimax Location Problems, Transportation Science, Vol. 15, 164-166 (1981)

[2] R. Chandrasekaran and A. Tamir, Optimization Problems with Algebraic Solutions: Quadratic Fractional Programs and Ratio Games, Mathematical Programming, Vol. 30, 326-339 (1984)

[3] G. Chrystal, On the Problem to Construct the Minimum Circle Enclosing n Given Points in the Plane, in Proceedings of the Edinburgh Mathematical Society, 3, 30-33 (1885)

[4] J. Elzinga and D.W. Hearn, The Minimum Covering Sphere Problem, Management Science, Vol. 19, 96-104 (1972)

[5] J. Elzinga and D.W. Hearn, Geometric Solutions for Some Minimax Location Problems, Transportation Science, Vol. 6, 379-394 (1972)

[6] J. Elzinga, D.W. Hearn and W.D. Randolph, Minimax Multifacility Location with Euclidean Distances, Transportation Science, Vol. 10, 321-336 (1976)

[7] Francis, R.L., L. F. McGinnis and J.A. White, Facility Layout and Location: An Analytical Approach, Second edition, Prentice-Hall, Inc., Englewood Cliffs, N.J. (1992)

[8] D.W. Hearn and J. Vijay, Efficient Algorithms for the (Weighted) Minimum Circle Problem, Operations Research, Vol. 30, No. 4, 777-795 (1982)

[9] S.K. Jacobsen, An Algorithm for the Minimax Weber Problem, European Journal of Operational Research, Vol. 6, 144-148 (1981)

[10] P. Kumar and E.A. Yildirim, A Core Set Result for the Weighted Euclidean One-Center Problem, Informs Journal on Computing, to appear (2009)

[11] C.L. Lawson, The Smallest Covering Cone or Sphere, SIAM Review, 415-417 (1965)

[12] N. Megiddo, Linear-Time Algorithms for Linear Programming in R3 and Related Problems, SIAM Journal on Computing, Vol. 12, 759-776 (1983)

[13] N. Megiddo, The Weighted Euclidean 1-Center Problem, Mathematics of Operations Research, Vol. 8, 498-504 (1983)

[14] N. Megiddo, Applying Parallel Algorithms in the Design of Serial Algorithms, Journal Assoc. Comput. Mach., Vol. 30, 852{865, (1983)

[15] N. Megiddo and E. Zemel, An O(n log n) Randomizing Algorithm for the Weighted Euclidean 1-Center Problem, Journal of Algorithms, VOl. 7, 358-368 (1986)

[16] M.I. Shamos and D. Hoey, Closest Point Problems, in Proceedings of 16 th Annual IEEE Symposium on Foundations of Computer Science, 151{162 (1975)

[17] S. Skyum, A Simple Algorithm for Computing the Smallest Enclosing Circle, Information Processing Letters, Vol. 37, 121-125 (1991)

[18] J.J. Sylvester, A Question in the Geometry of Situation, Quarterly Journal of Mathemaitcs, Vol. 1, p. 79 (1857)

[19] J.J. Sylvester, On Poncelet's Approximate Linear Valuation of Surd Forms, Philosophical Magazine, Vol. 20, 203-222 (1860)

[20] E.Welzl, Smallest Enclosing Disks (Balls and Ellipsoids), in H. Maurer (Ed.), New Results and New Trends in Computer Science, Lecture Notes in Computer Science, Vol. 555, Springer-Verlag, 359-37 (1991)

[21] S. Xu , R.M. Freund and J. Sun, Solution Methodologies for the Smallest Enclosing Circle Problem, Computational Optimization and Applications, Vol. 25, 283-292 (2003)

[22] G.L. Zhou , K.C. Tohemail and J. Sun, E±cient Algorithms for the Smallest Enclosing Ball Problem, Computational Optimization and Applications, Vol. 30, 147-160 (2005)

External links

• Bernd Gärtner's smallest enclosing ball code
• Miniball open source project for smallest enclosing balls