Last week, I proved Helly’s theorem and discussed an application called Kirchberger’s theorem. I want to follow up with another, not surprisingly, geometric application in the form of enclosing a finite set of points in the plane by a circle of minimal radius. This is known as the “smallest circle” or “minimal enclosing ball” problem. Such a circle exists, and is unique. The generalization, which we will prove, to points in -dimensional space is true as well.
Recall that the diameter of a bounded set in is defined as
Of course, the diameter of a set makes sense in arbitrary metric spaces, but we will restrict our attention to Euclidean space. It is clear that any closed ball containing must have radius at least and that any closed ball of radius centered at one of the points of will contain . Can we do better than for all such sets ? Jung’s theorem tells us that we can! Specifically, any bounded set of diameter is contained in a closed ball of radius .
You may be thinking this is all very well and good, but what does Helly’s theorem have to do with the minimal enclosing ball? Helly’s theorem doesn’t play a role in the proof of either the existence or the uniqueness of the minimal enclosing ball, but it will be needed in the proof of Jung’s theorem.
The plan is to first prove the existence and uniqueness of the minimal enclosing ball. I will not discuss algorithms for computing said ball, but a quick Google search will show the interested reader that this is well-studied topic in the literature. Armed with the knowledge such an optimal ball always exist, we will then prove Jung’s theorem.
Let be a bounded subset.
Lemma. If has a minimal enclosing ball , then this ball is unique.
Proof. Suppose and are two balls of minimal radius centered at and , respectvely, containing . Suppose , set , and set . I claim that the open ball contains . Suppose . Then by the parallelogram law,
which implies that .
To prove the existence of the minimal enclosing ball of a set $latex $, we use a limit argument. Let be the infimum of the radii of balls . It is clear that is bounded from below by . Let be a sequence of radii decreasing to with corresponding centers . I claim that is a Cauchy sequence in . Indeed, for any indices , we have by the parallelogram law that
for any . Our argument above shows that is contained in the open ball , which implies the upper bound
as . By completeness, has limit . I claim that . Indeed, by the continuity of the norm,
An alternative characterization of is the necessarily unique minimizer of the function
Now let , where , be a finite set containing at least two points.
Lemma. If has a minimal enclosing ball , then there exist at least two points that lie on the boundary . In fact, if is a hyperplane through the center , then the intersection of with either of the closed half-planes and must contain at least one point.
Proof. Suppose that has a minimum enclosing ball such that only one point lies on the boundary. For any point , . Set , and note by the previous observation that . Consider the line segment through and , which we parametrize by , with . If we choose so that , then
and . Hence, the closed ball centered at and with radius also encloses , which contradicts the uniqueness of the minimal enclosing ball.
Theorem. (Jung’s theorem) Suppose is bounded with diameter . Then is contained in a closed ball of radius .
Proof. We first prove Jung’s theorem in the case is finite and . Let denote the center of the ball containing of minimum radius . Translating , we may assume without loss of generality that . Enumerate the elements of by (note that , as shown above). It follows from the uniqueness of the minimum enclosing ball of that , and therefore we can write
For any ,
where we use the fact that and the linearity of the inner product to obtain the ultimate equality. Since , this last expression is just . Summing over , we obtain
where the last equality follows from the fact that the function is increasing on and .
We now prove Jung’s theorem for an arbitrary bounded set . For each point in , consider the open ball . For any balls with centers , I claim that the intersection of the balls is nonempty. Let denote the center of the ball enclosing of minimum radius . Since the diameter of the set is , our work above shows that
which implies that
By Helly’s theorem,
The conclusion of the theorem follows by centering a ball at some point in the intersection.