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. This problem is also called minimum covering circle problem. 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. 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.

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, Failed to parse (unknown function "\math"): {\displaystyle A = C<\math> if angle <math>\angle BAC} is obtuse or Failed to parse (unknown function "\math"): {\displaystyle B = C <\math> if angle <math>\angle ABC} is obtuse and go to Step 2.

External links

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