Smallest-circle problem

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.

{{Collapse top|title=Proof that the minimum covering disk is unique}}

Let {{var|P}} be any set of points in the plane, and suppose that there are two smallest enclosing disks of {{var|P}}, with centers at $\backslash vec\{z\}\_1$ and $\backslash vec\{z\}\_2$. Let $r$ be their shared radius, and let $2a$ be the distance between their centers. Since {{var|P}} is a subset of both disks it is a subset of their intersection. However, their intersection is contained within the disk with center $\backslash frac\; 12\; (\backslash vec\{z\}\_1+\backslash vec\{z\}\_2)$ and radius $\backslash sqrt\{r^2-a^2\}$, as shown in the following image:

:300px

Since {{var|r}} is minimal, we must have $\backslash sqrt\{r^2-a^2\}=r$, meaning $a=0$, so the disks are identical.{{sfn|Welzl|1991|p=2}}

{{Collapse bottom}}

As Nimrod Megiddo showed,{{citation

| last = Megiddo | first = Nimrod | author-link = Nimrod Megiddo

| doi = 10.1137/0212052

| issue = 4

| journal = SIAM Journal on Computing

| mr = 721011

| pages = 759–776

| title = Linear-time algorithms for linear programming in {{math|R³}} and related problems

| volume = 12

| year = 1983| s2cid = 14467740 }}. 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(n^3)$ and $O(n\; \backslash log\; n)$ algorithms; in doing so, Megiddo demonstrated that Shamos and Hoey's conjecture – that a solution to the smallest-circle problem was computable in $\backslash Omega(n\; \backslash log\; n)$ at best – was false.{{citation|first1=M. I.|last1=Shamos|author1-link=Michael Ian Shamos|first2=D.|last2=Hoey|contribution=Closest point problems|title=Proceedings of 16th Annual IEEE Symposium on Foundations of Computer Science|pages=151–162|year=1975|doi=10.1109/SFCS.1975.8|title-link=Symposium on Foundations of Computer Science|s2cid=40615455 }}

Emo Welzl{{citation

| last = Welzl | first = Emo | author-link = Emo Welzl

| editor-last = Maurer | editor-first = H.

| doi = 10.1007/BFb0038202

| contribution = Smallest enclosing disks (balls and ellipsoids)

| volume = 555

| pages = 359–370

| publisher = Springer-Verlag

| series = Lecture Notes in Computer Science

| title = New Results and New Trends in Computer Science

| year = 1991| isbn = 978-3-540-54869-0 | citeseerx = 10.1.1.46.1450 }}. proposed a simple randomized algorithm for the

minimum covering circle problem that runs in expected time $O(n)$, 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 $O(n)$ time bound, which was factorial for Seidel's method, could be reduced to subexponential.{{citation

| last1 = Matoušek | first1 = Jiří | author1-link = Jiří Matoušek (mathematician)

| last2 = Sharir | first2 = Micha | author2-link = Micha Sharir

| last3 = Welzl | first3 = Emo

| doi = 10.1007/BF01940877

| journal = Algorithmica

| pages = 498–516

| title = A subexponential bound for linear programming

| url = http://www.inf.ethz.ch/personal/emo/PublFiles/SubexLinProg_ALG16_96.pdf

| volume = 16

| issue = 4–5 | year = 1996| citeseerx = 10.1.1.46.5644 | s2cid = 877032 }}.

Welzl's minidisk algorithm has been extended to handle Bregman divergences{{citation| first1=Frank|last1=Nielsen|first2=Richard |last2=Nock |

title=On the smallest enclosing information disk|journal=Information Processing Letters|volume=105|issue=3|pages=93-97|year=2008|doi=10.1016/j.ipl.2007.08.007}} which include the squared Euclidean distance.

File:Megiddo's minimum enclosing circle algorithm prune stage2.png

Megiddo's algorithm{{citation

| last = Megiddo | first = Nimrod | author-link = Nimrod Megiddo

| doi = 10.1137/0212052

| issue = 4

| journal = SIAM Journal on Computing

| mr = 721011

| pages = 759–776

| title = Linear-time algorithms for linear programming in {{math|R³}} and related problems

| volume = 12

| year = 1983| s2cid = 14467740 }}. is based on the technique called prune and search, reducing the size of the problem by removing $\backslash frac\{n\}\{16\}$ unnecessary points.

That leads to the recurrence $t(n)\; \backslash le\; t\backslash left(\backslash frac\{15n\}\{16\}\backslash right)+cn$ giving $t(n)=16cn$.

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 $\backslash frac\{n\}\{16\}$ points to be discarded are found as follows:

The points {{var|P_i}} are arranged into pairs which defines $\backslash frac\{n\}\{2\}$ lines {{var|p_j}} as their bisectors.

The median average {{var|p_m}} of bisectors in order by their directions (oriented to the same half-plane determined by bisector {{math|p₁}}) is found and pairs of bisectors are made, such that in each pair one bisector has direction at most {{var|p_m}} and the other at least {{var|p_m}}

(direction {{math|p₁}} could be considered as −$\backslash infty$ or +$\backslash infty$ according our needs.) Let {{var|Q_k}} be the intersection of the bisectors in the {{var|k}}-th pair.

The line q in the {{math|p₁}} direction is placed to go through an intersection {{var|Q_x}} such that there are $\backslash frac\{n\}\{8\}$ intersections in each half-plane defined by the line (median position).

The constrained version of the enclosing problem is run on the line q' which determines half-plane where the center is located.

The line q′ in the {{var|p_m}} direction is placed to go through an intersection {{var|Q_x'}} such that there are $\backslash frac\{n\}\{16\}$ intersections in each half of the half-plane not containing the solution.

The constrained version of the enclosing problem is run on line q′ which together with q determines the quadrant where the center is located.

We consider the points {{var|Q_k}} in the quadrant not contained in a half-plane containing the solution.

One of the bisectors of the pair defining {{var|Q_k}} has the direction ensuring which of points {{var|P_i}} 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 the problem size by removal of $\backslash frac\{n\}\{4\}$ points leading to recurrence

:$t(n)\; \backslash le\; t\backslash left(\backslash frac\{3n\}\{4\}\backslash right)+cn$

giving $t(n)\; =\; 4cn$.

The $\backslash frac\{n\}\{4\}$ points to be discarded are found as follows:

Points {{var|P_i}} are arranged into pairs.

For each pair, the intersection {{var|Q_j}} of its bisector with the constraining line {{var|q}} is found (If this intersection does not exist we could remove one point from the pair immediately).

The median {{var|M}} of points {{var|Q_j}} on the line {{var|q}} is found and in O(n) time is determined which halfline of {{var|q}} starting in {{var|M}}

contains the solution of the constrained problem.

We consider points {{var|Q_j}} from the other half.

We know which of the points {{var|P_i}} defining {{var|Q_j}} 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 {{var|P_i}} 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.)

The algorithm is recursive.

The initial input is a set P of points. The algorithm selects one point p randomly and uniformly from P, and recursively finds the minimal circle containing P – {p}, i.e. all of the other points in P except p. If the returned circle also encloses p, it is the minimal circle for the whole of P and is returned.

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.

algorithm welzl is

input: Finite sets P and R of points in the plane |R| ≤ 3.

output: Minimal disk enclosing P with R on the boundary.

if P is empty or |R| = 3 then

return trivial(R)

choose p in P (randomly and uniformly)

D := welzl(P − {p}, R)

if p is in D then

return D

return welzl({{var|P}} − {p}, R ∪ {p})

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(n⁴) 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{{citation|first1=R. K.|last1=Chakraborty|first2=P. K.|last2=Chaudhuri|title=Note on geometrical solutions for some minimax location problems|journal=Transportation Science|volume=15|issue=2|pages=164–166|year=1981|doi=10.1287/trsc.15.2.164|doi-access=free}}. 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(nh).
• Elzinga and Hearn{{citation|first1=J.|last1=Elzinga|first2=D. W.|last2=Hearn|title=Geometrical solutions for some minimax location problems|journal=Transportation Science|volume=6|issue=4|pages=379–394|year=1972|doi=10.1287/trsc.6.4.379}}. 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(h³n), the authors report that it ran in linear time in their experiments. The complexity of the method has been analyzed by Drezner and Shelah.{{citation|first1=Zvi|last1=Drezner|first2=Saharon|last2=Shelah|authorlink2=Saharon Shelah|title=On the complexity of the Elzinga–Hearn algorithm for the 1-center problem|journal=Mathematics of Operations Research|volume=12|issue=2|pages=255–261|year=1987|jstor=3689688|doi=10.1287/moor.12.2.255}}. Both Fortran and C codes are available from {{harvtxt|Hearn|Vijay|Nickel|1995}}.{{citation|first1= D. W.|last1=Hearn|first2=J.|last2=Vijay|first3=S.|last3=Nickel|title=Codes of geometrical algorithms for the (weighted) minimum circle problem|journal=European Journal of Operational Research|volume=80|pages=236–237|year=1995|doi=10.1016/0377-2217(95)90075-6}}.
• 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.{{citation|first=S. K.|last=Jacobsen|title=An algorithm for the minimax Weber problem|journal=European Journal of Operational Research|volume=6|issue=2|pages=144–148|year=1981|doi=10.1016/0377-2217(81)90200-9}}. Hearn and Vijay{{citation|first1=D. W.|last1=Hearn|first2=J.|last2=Vijay|title=Efficient algorithms for the (weighted) minimum circle problem|journal=Operations Research|volume=30|issue=4|pages=777–795|year=1982|doi=10.1287/opre.30.4.777}}. 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;{{citation|first1=J.|last1=Elzinga|first2=D. W.|last2=Hearn|first3=W. D.|last3=Randolph|title=Minimax multifacility location with Euclidean distances|journal=Transportation Science|volume=10|issue=4|pages=321–336|year=1976|doi=10.1287/trsc.10.4.321}}. an algorithm of Lawson{{citation|first=C. L.|last=Lawson|title=The smallest covering cone or sphere|journal=SIAM Review|volume=7|issue=3|doi=10.1137/1007084|pages=415–417|year=1965}}. can be described in this way as a primal dual algorithm.
• Shamos and Hoey proposed an O(n log n) 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.

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 (i.e., distance multiplied by the corresponding weight) to any point. The original (unweighted) minimum covering circle problem corresponds to the case when all weights are equal to 1. 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.{{citation|first=N.|last=Megiddo|author-link=Nimrod Megiddo|title=The weighted Euclidean 1-center problem|journal=Mathematics of Operations Research|volume=8|issue=4|pages=498–504|year=1983|doi=10.1287/moor.8.4.498}}.{{citation|first1=N.|last1=Megiddo|author1-link=Nimrod Megiddo|first2=E.|last2=Zemel|title=An O(n log n) randomizing algorithm for the weighted Euclidean 1-center problem|journal=Journal of Algorithms|volume=7|issue=3|pages=358–368|year=1986|doi=10.1016/0196-6774(86)90027-1}}.

The smallest enclosing ball of a finite point set has been studied in Riemannian geometry including Cartan-Hadamard manifolds.{{citation | first1=Marc | last1=Arnaudon | first2=Frank| last2=Nielsen |title=On approximating the Riemannian 1-center|journal=Computational Geometry|volume=46|issue=1| pages=93-104| year=2013| doi=10.1016/j.comgeo.2012.04.007| arxiv=1101.4718}}

• Bounding sphere
• 1-center problem
• Circumscribed circle
• Closest string
• Jung's Theorem
• Minimum-diameter spanning tree

{{reflist|colwidth=30em}}

• [http://www.inf.ethz.ch/personal/gaertner/miniball.html Bernd Gärtner's smallest enclosing ball code]
• [http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Bounding_volumes/Chapter_main.html CGAL] the Min_sphere_of_spheres package of the Computational Geometry Algorithms Library (CGAL)
• [https://github.com/hbf/miniball Miniball] an open-source implementation of an algorithm for the smallest enclosing ball problem for low and moderately high dimensions

Category:Computational geometry

Category:Combinatorial optimization

Category:Circles