Minimal circle containing set of points

Question

Suppose that there are $n$ points in the plane $x_1, x_2, \dots x_n$, and $C$ is the minimal circle (the circle with the minimal radius) that contains all of them. If there is another point $p$ outside of $C$, then how can one prove that $p$ is lying on the minimal circle containing $x_1, \dots , x_n, p$? It looks so intuitive, but I can't find a way to prove it... Any help?

Answer 1

Let $D$ be the disk bounded by the radius minimizing circle $\partial D = C\{{x_1, \dots, x_n\}}$. Two outcomes, $p \in D$ or $p \notin D$.

If $p \notin C\{x_1, \dots, x_n, p\}$ then $p$ is inside the disk $D$ bounded by $C\{{x_1, \dots, x_n\}}$. But we assumed $p \notin D$.

---

This is an instance of the problem of Appolonius. By induction, we are looking for the smallest circle $C_1 = C\{x_1, \dots, x_n, p\}$ which contains $p$ and $C_0 = C\{{x_1, \dots, x_n\}}$.

If $p$ is not inside $C_0$, then $C_1$ should be tangent $C_0$ and go through $p$. For this case of the Appolonius problem, you actually need two points to specify a unique circle.

In other words, there are infinitely circles $C_1$ passing through $p$ and tangent to $C_0$. One of these has the smallest radius.

---

The above is not quite true... instead of $C_1$ being tangent to $C_0$ and $p$, just $C_1$ goes through $p$ and its tangent to the convex hull, $\overline{\{x_1, \dots, x_n \}}$.

Lemma The diameter of the minimal circle is the same as the diameter of the convex hull The minimizing circle cuts through at least three points in the set. Generically, exactly 3.

The circle needs surround all the points so the diameter is at least that of the convex hull, but it can be bigger. If the min circle didn't go through any points, we could shrink the radius so it passes through at least one. In fact, since 3 points determine a circle, we can shrink the radius until it passes through at least 3. Generically, there shouldn't be a fourth point exactly on the circle.

So we can run through all $\binom{n}{3}$ triples of points, verify the circumcircle contains all the other points, and find the one with the smallest radius. For the induction, we adjoin $p$ and iterate through the $\binom{n+1}{3}$ points.

---

I found graphic in a graduate Computer Science course, on the "Minimal Enclosing Circle" problem. Wikipedia calls this the "Smallest Circle Problem" and attributes it to Mathematician James Joseph Sylvester. This question was also asked on the StackOverflow programming site:

• https://stackoverflow.com/questions/4901535/smallest-circle-which-covers-given-points-on-2d-plane
• Is this a wrong solution to the smallest enclosing circle problem?

It was a computer science homework for sophomores at Princeton (Cos 226) Literature points to a fast solution by Emo Welzl. The paper is called Smallest Enclosing Disks (Balls and Ellipsoids)

---

Proposition the radius minimizing circle is unique

For contradiction, if we have two circles $C, C'$ which contain all $n$ points, these points must lie in the intersection of the two circles $C \cap C'$. The intersection of these two circles is a lens shape with diameter smaller than that of $C$ or $C'$.

This diameter determines a circle still containing all $n$ points, but with diameter smaller than that of $C$ or $C'$.

Answer 2

For any set of different points $x$, the circular hull (the minimal circle containing all points) of $x$ is equal to the circular hull of a subset of $x$, that subset having exactly $2$ or $3$ points. There may be multiple subsets, but there is at least $1$.

There is then exactly $1$ point $c$ that is equidistant $r$ from those $3$ points (or the midpoint of $2$ points). This $c$ is the center of the circular hull.

Every other point has a distance to $c$ which is less than or equal to $r$. The question assumes that the distance of $p$ to $c$ is greater than $r$.

$x \cup \{p\}$ also has a subset of $2$ or $3$ points that determines its circular hull.

The claim is that every such subset of points which has the same circular hull as $x \cup \{p\}$ must contain $p$.

Consider a $y$ such that : $y \subseteq x$, $|y| = 3$ or $|y| = 2$, $p \not \in y$

If that $y$ formed a circular hull of $x \cup \{p\}$ then it also forms a circular hull of $x$. But in the former case, the distance of $p$ to the center is less than the radius of the circular hull and in the latter case it contradicts the assumption of that $p$ is outside of the circular hull of $x$.

So all such $y$ cannot be a circular hull of $x \cup \{p\}$ so all subsets of points determining the circular hull of $x \cup \{p\}$ must contain $p$.

Answer 3

It is so because these are circles. The center and radius of C is known. Draw a perpendicular from outside point p onto circle $C$ having a diameter $\phi_C$ . Let this outside distance along normal be $d$.

The new minimal circle diameter containing point $p$ and $C$ is $ \phi_C + d $ because line length $d$ is added along diameter of C.