Minimal circle containing set of points

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?

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'$.

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.