## Helly’s Theorem and Applications II: Jung’s Theorem

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 $\mathbb{R}^{2}$ 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 $d$-dimensional space is true as well.

Recall that the diameter of a bounded set $S$ in $\mathbb{R}^{d}$ is defined as

$\text{diam}(S):=\sup_{x,y\in S}\left\|x-y\right\|$

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 $S$ must have radius at least $\frac{r}{2}$ and that any closed ball of radius $r$ centered at one of the points of $S$ will contain $S$. Can we do better than $r$ for all such sets $S$? Jung’s theorem tells us that we can! Specifically, any bounded set $S\subset\mathbb{R}^{d}$ of diameter $\alpha$ is contained in a closed ball of radius $\sqrt{\frac{d}{2d+2}}\cdot\alpha$.

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 $S\subset\mathbb{R}^{d}$ be a bounded subset.

Lemma. If $S$ has a minimal enclosing ball $B$, then this ball is unique.

Proof. Suppose $B_{1}=B(x;r)$ and $B_{2}=B(y;r)$ are two balls of minimal radius $r$ centered at $x=(x_{1},\cdots,x_{d})$ and $y=(y_{1},\cdots,y_{d})$, respectvely, containing $S$. Suppose $x\neq y$, set $\alpha :=\frac{\left\|x-y\right\|}{2}$, and set $c:=\frac{x+y}{2}$. I claim that the open ball $B=B(c;\sqrt{r^{2}-\alpha^{2}})$ contains $S$. Suppose $z\in B_{1}\cap B_{2}$. Then by the parallelogram law,

$\begin{array}{lcl}\displaystyle\left\|z-c\right\|^{2}=\frac{1}{4}\left\|(z-x)+(z-y)\right\|^{2}&=&\displaystyle\frac{1}{2}[\left\|z-x\right\|^{2}+\left\|z-y\right\|^{2}]-\frac{1}{4}\left\|y-x\right\|^{2}\\[.9 em]&\leq&\displaystyle r^{2}-\alpha^{2}\end{array}$

which implies that $B_{1}\cap B_{2}\subset B$. $\Box$

To prove the existence of the minimal enclosing ball of a set $latex$, we use a limit argument. Let $r$ be the infimum of the radii of balls $B(c;r')$. It is clear that $r$ is bounded from below by $\frac{1}{2}\text{diam}(S)$. Let $(r_{n})_{n=1}^{\infty}$ be a sequence of radii decreasing to $r$ with corresponding centers $c_{n}$. I claim that $(c_{n})_{n=1}^{\infty}$ is a Cauchy sequence in $\mathbb{R}^{d}$. Indeed, for any indices $n,m$, we have by the parallelogram law that

$\displaystyle\left\|c_{n}-c_{m}\right\|^{2}=2\left\|c_{n}-z\right\|^{2}+2\left\|c_{m}-z\right\|^{2}-\left\|c_{n}+c_{m}-2z\right\|^{2}$,

for any $z\in S$. Our argument above shows that $S$ is contained in the open ball $B(\frac{c_{n}+c_{m}}{2};r)$, which implies the upper bound

$\displaystyle\left\|c_{n}-c_{m}\right\|^{2}\leq2\left\|c_{n}-z\right\|^{2}+2\left\|c_{m}-z\right\|^{2}-4r^{2}\longrightarrow 2r^{2}+2r^{2}-4r^{2}=0$,

as $n,m\rightarrow\infty$. By completeness, $c_{n}$ has limit $c\in\mathbb{R}^{d}$. I claim that $S\subset\overline{B}(c;r)$. Indeed, by the continuity of the norm,

$\displaystyle\forall z\in S, \indent \left\|c-z\right\|=\lim_{n\rightarrow\infty}\left\|c_{n}-z\right\|\leq\lim_{n\rightarrow\infty}r_{n}=r$

An alternative characterization of $c$ is the necessarily unique minimizer of the function

$\displaystyle f:\mathbb{R}^{d}\rightarrow[0,\infty),\indent f(x):=\sup_{y\in S}\left\|x-y\right\|$

Now let $S\subset\mathbb{R}^{d}$, where $d\geq 2$, be a finite set containing at least two points.

Lemma. If $S$ has a minimal enclosing ball $B(c;r)$, then there exist at least two points $x,y\in S$ that lie on the boundary $\partial B(c;r)$. In fact, if $H=\left\{x\in\mathbb{R}^{d}: \right\}$ is a hyperplane through the center $c$, then the intersection of $\partial B(c;r)$ with either of the closed half-planes $H^{+}$ and $H^{-}$ must contain at least one point.

Proof. Suppose that $S$ has a minimum enclosing ball $\overline{B}(c;r)$ such that only one point $x\in S$ lies on the boundary. For any point $y\in\text{int}B(c;r)\cap S$, $\left\|c-y\right\|. Set $r':=\max_{y\in S\setminus\left\{x\right\}}\left\|c-y\right\|$, and note by the previous observation that $\alpha. Consider the line segment through $x$ and $c$, which we parametrize by $tx+(1-t)c$, with $t\in[0,1]$. If we choose $t$ so that $tr+(1-t)r', then

$\begin{array}{lcl}\displaystyle\left\|y-tx-(1-t)c\right\|\leq t\left\|y-x\right\|+(1-t)\left\|y-c\right\|&=&\displaystyle tr+(1-t)\left\|y-c\right\|\\&\leq&\displaystyle tr+(1-t)r'\\&<&\displaystyle r\end{array}$

and $\left\|x-tx-(1-t)c\right\|=(1-t)\left\|x-c\right\|. Hence, the closed ball centered at $c'=tx+(1-t)c$ and with radius $\max\left\{(1-t)r,tr+(1-t)r'\right\}$ also encloses $S$, which contradicts the uniqueness of the minimal enclosing ball. $\Box$

Theorem. (Jung’s theorem) Suppose $S\subset\mathbb{R}^{d}$ is bounded with diameter $\text{diam}(S)$. Then $S$ is contained in a closed ball of radius $(\frac{d}{2d+2})^{\frac{1}{2}}\text{diam}(S)$.

Proof. We first prove Jung’s theorem in the case $S$ is finite and $\left|S\right|\leq d+1$. Let $c$ denote the center of the ball containing $S$ of minimum radius $r$. Translating $S$, we may assume without loss of generality that $c=0$. Enumerate the elements of $\left\{x\in S: \left\|x\right\|=r\right\}$ by $x_{1},\cdots,x_{n}$ (note that $n\geq 2$, as shown above). It follows from the uniqueness of the minimum enclosing ball of $S$ that $c\in\text{co}(x_{1},\cdots,x_{n})$, and therefore we can write

$\displaystyle c=\sum_{k=1}^{n}\lambda_{k}x_{k},\indent\lambda_{k}\geq0,\indent\sum_{k=1}^{n}\lambda_{k}=1$

For any $i\in\left\{1,\cdots,n\right\}$,

$\begin{array}{lcl}\displaystyle1-\lambda_{i}=\sum_{{k=1}\atop{k\neq i}}^{n}\lambda_{k}\geq\sum_{{k=1}\atop{k\neq i}}^{n}\lambda_{k}\frac{\left\|x_{k}-x_{i}\right\|^{2}}{\text{diam}(S)^{2}}&=&\displaystyle\sum_{k=1}^{n}\lambda_{k}\frac{x_{i}^{2}+x_{k}^{2}-2\langle{x_{i},x_{k}}\rangle}{\text{diam}(S)^{2}}\\&=&\displaystyle\frac{1}{\text{diam}(S)^{2}}\left[2r^{2}-2\left\langle{\sum_{k=1}^{n}\lambda_{k}x_{k},x_{i}}\right\rangle\right],\end{array}$

where we use the fact that $\sum_{k=1}^{n}\lambda_{k}=1$ and the linearity of the inner product to obtain the ultimate equality. Since $\sum_{k=1}^{n}\lambda_{k}x_{k}=c=0$, this last expression is just $\frac{2r^{2}}{\text{diam}(S)^{2}}$. Summing $1-\lambda_{i}$ over $i\in\left\{1,\cdots,n\right\}$, we obtain

$\displaystyle n-1\geq\frac{2nr^{2}}{\text{diam}(S)^{2}}\Longleftrightarrow r\leq\left(\frac{n-1}{2n}\right)^{\frac{1}{2}}\text{diam}(S)\leq\left(\frac{d}{2d+2}\right)^{\frac{1}{2}}\text{diam}(S)$,

where the last equality follows from the fact that the function $x\mapsto\frac{x-1}{2x}$ is increasing on $(0,\infty)$ and $n\leq d+1$.

We now prove Jung’s theorem for an arbitrary bounded set $S$. For each point in $x$, consider the open ball $B(x;(\frac{d}{2d+2})^{\frac{1}{2}}\text{diam}(S))$. For any $d+1$ balls with centers $x_{1},\cdots,x_{d+1}$, I claim that the intersection of the $d+1$ balls is nonempty. Let $c$ denote the center of the ball enclosing $\left\{x_{1},\cdots,x_{d+1}\right\}$ of minimum radius $r$. Since the diameter of the set $\left\{x_{1},\cdots,x_{d+1}\right\}$ is $\leq\text{diam}(S)$, our work above shows that

$\displaystyle r\leq\left(\frac{d}{2d+2}\right)^{\frac{1}{2}}\text{diam}(S)$,

which implies that

$\displaystyle c\in\bigcap_{j=1}^{d+1}B\left(x_{j};(\frac{d}{2d+2})^{\frac{1}{2}}\text{diam}(S)\right)$

By Helly’s theorem,

$\displaystyle\bigcap_{x\in S}B\left(x;(\frac{d}{2d+2})^{\frac{1}{2}}\text{diam}(S)\right)\neq\emptyset$

The conclusion of the theorem follows by centering a ball at some point $c$ in the intersection. $\Box$

About these ads
This entry was posted in Classical Analysis, Combinatorics, Convexity and tagged , , , . Bookmark the permalink.