## Jung’s Theorem

Given a set of points of diameter ${D}$ in ${n}$ dimensional Euclidean space ${{\bf R}^n}$ it is trivial to see that it can be covered by a ball of radius ${D}$. But the following theorem by Jung improves the result by a factor of about ${\frac{1}{\sqrt{2}}}$, and is the best possible.
Theorem 1 [ Jung’s Theorem: ] Let ${S}$ be a set of points in ${{\bf R}^n}$ of diameter ${D}$. Then there is a ball of radius ${\sqrt{\frac{n}{2n + 2}} D}$ covering ${S}$.
Proof: We first prove this theorem for sets of points ${S}$ with ${\vert S \vert \leq n + 1}$ and then extend it to an arbitrary point set. If ${\vert S \vert \leq n + 1}$ then the smallest ball enclosing ${S}$ exists. We assume that its center is the origin. Denote its radius by ${r}$. Denote by ${S' \subseteq S}$ the subset of points such that ${||p|| = r}$ for ${p \in S'}$. It is easy to see that ${S'}$ is in fact non empty.

Observation: The origin must lie in the convex hull of ${S'}$. Assuming the contrary, there is a separating hyperplane ${H}$ such that ${S'}$ lies on one side and the origin lies on the other side of ${H}$ (strictly). By assumption, every point in ${S \setminus S'}$ is distance strictly less than ${r}$ from the origin. Move the center of the ball slightly from the origin, in a direction perpendicular to the hyperplane ${H}$ towards ${H}$ such that the distances from the origin to every point in ${S \setminus S'}$ remains less than ${r}$. However, now the distance to every point of ${S'}$ is decreased and so we will have a ball of radius strictly less than ${r}$ enclosing ${S}$ which is a contradiction to the minimality of ${r}$.

Let ${S' = \{ p_1, p_2,\dots, p_m\}}$ where ${m \leq n \leq d+1}$ and because the origin is in the convex hull of ${S'}$ so we have nonnegative ${\lambda_i}$ such that,

$\displaystyle \sum \lambda_i p_i = 0, \sum \lambda_i = 1$

Fix a ${k, 1 \leq k \leq m}$. Then we have,
$\displaystyle \begin{array}{rcl} 1 - \lambda_k &=& \sum_{i \neq k} \lambda_i \\ &\geq& \frac{1}{D^2}\sum_{i = 1}^m \lambda_i || p_i -p_k ||^2 \\ &=& \frac{1}{D^2}\left ( \sum_{i=1}^m \lambda_i (2r^2 - 2 \langle p_i, p_k \rangle) \right ) \\ &=& \frac{1}{D^2} \left ( 2r^2 - 2 \left \langle \sum_{i=1}^m \lambda_i p_i, p_k \right \rangle \right ) \\ &=& \frac{2r^2}{D^2} \end{array}$

Adding up the above inequalities for all values of ${k}$, we get
$\displaystyle \begin{array}{rcl} m - 1 \geq 2m r^2 / D^2 \end{array}$

Thus we get ${\frac{r^2}{D^2} \leq m - 1 / 2m \leq \frac{n}{2n + 2}}$ since ${m \leq n + 1}$ and the function $(x-1)/2x$ is monotonic. So we have immediately ${r \leq \sqrt{\frac{n}{2n+2}} D}$.
The remainder of the proof uses the beautiful theorem of Helly. So assume ${S}$ is any set of points of diameter ${D}$. With each point as center draw a ball of radius ${r = \sqrt{\frac{n}{2n+2}}D}$. Clearly any ${n + 1}$ of these balls intersect. This is true because the center of the smallest ball enclosing ${n+1}$ of the points is at most ${r}$ away from each of those points. So we have a collection of compact convex sets, any ${n+1}$ of which have a nonempty intersection. By Helly’s theorem all of them have an intersection. Any point of this intersection can be chosen to be the center of a ball of radius ${r}$ that will enclose all of ${S}$. $\Box$