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

Advertisements

One Response to Jung’s Theorem

  1. asd says:

    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)

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

%d bloggers like this: