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\|<r. Set r':=\max_{y\in S\setminus\left\{x\right\}}\left\|c-y\right\|, and note by the previous observation that \alpha<r. 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'<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\|<r. 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

Advertisements
This entry was posted in math.CA, math.CO and tagged , , , . Bookmark the permalink.

One Response to Helly’s Theorem and Applications II: Jung’s Theorem

  1. Pingback: Circumscribed Circle vs. Minimum Enclosing Circle I | Math by Matt

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s