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$

Like this:

Be the first to like this post.

This entry was posted on Saturday, August 7th, 2010 at 5:43 pm and is filed under Convex and Discrete Geometry, Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to Jung’s Theorem

asd says:

July 6, 2011 at 8:59 am

this proof is missing a small step: (m-1)/2m <= n/(2n+2) since the function (x-1)/2x is monotonic.

Thanks. Step added! (cstheory)

Reply

	asd on Jung’s Theorem
	claude on Tensor Calculus II
	Harish Prabhu on Some pointers for computer tro…
	Akash Kumar on Superconcentrators From E…
	Akash Kumar on Superconcentrators From E…

The Algorithmic Lens

Jung’s Theorem

Like this:

One Response to Jung’s Theorem

Leave a Reply Cancel reply

About

Computer Science

Mathematics

Other Interesting Blogs

Physics

Recent Comments

Top Posts

Categories

Archives

Meta

Blog Stats

Follow “The Algorithmic Lens”