Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a set of $n$ points in $\mathbb{R}^k$. The diameter of this set is the maximum distance between two of its points; its radius is the radius of the smallest (closed) k-ball that contains all the points.

If we know the diameter $d$, what can be said about the radius $r$? Clearly $d/2\leq r\leq d$, but can the upper bound be tightened?

share|improve this question
    
Do you want a bound that depends on $k$ or the best bound over all $k$? –  Phira Nov 19 '12 at 12:50
    
I’m interested in any bound better than $d$, whether dependent on $n$ and $k$ or not. –  Robin Houston Nov 19 '12 at 12:54
    
The point is that $d$ is the best bound unless you want to make it dependent on one of the parameters. –  Phira Nov 19 '12 at 12:57
    
Interesting, and surprising. Thanks. Do you have an example to prove that? –  Robin Houston Nov 19 '12 at 12:59
    
Ok, I am sorry, I spoke too quickly, I would have to recheck that. –  Phira Nov 19 '12 at 13:01

2 Answers 2

up vote 10 down vote accepted

The bound is given by Jung's Theorem, stated in sufficient generality at http://en.wikipedia.org/wiki/Jung%27s_theorem.

A sketch proof: start by considering simplices.

If all the $k+1$ vertices of a simplex in $\mathbb{R}^k$ lie on (the surface of) its minimum enclosing ball, then the M.E.B. is the circumsphere of that simplex. If not, then the $j+1$ vertices which do lie on the ball also lie on a vector subspace of dimension $j$ (and form a proper simplex within that subspace); the centre of the M.E.B. is the circumcentre of that sub-simplex and its radius is its circumradius.

Call a simplex whose M.E.B. is its circumsphere an acute simplex. (If $k = 2$ this definition captures the acute and right triangles, so it's a slight abuse.)

The regular $k$-simplex of edge $d$ has maximal circumradius among all acute $k$-simplices with diameter $d$. (I'm not entirely happy with my proof of this, so I won't write it up. It's easily shown to be a local maximum, though.)

To calculate this radius, let $r_k$ denote the circumradius of the regular $k$-simplex of side $1$. Observe that the circumcentre $c_S$ of an acute simplex $S$ with an acute face $R$ lies on the line normal to $R$ passing through $c_R$; write $h_k$ for the distance $||c_S-c_R||$ when $S$ is the regular $k$-simplex and $R$ one of its (regular $k-1$-simplex) faces. The remaining point of $S$ is collinear with $c_S$ and $c_R$. Considering the right triangles in this configuration, we see: $$r_k ^2 = r_{k-1}^2 + h_k^2 \mbox{ and }1 = (r_k + h_h)^2 + r_{k-1}^2.$$ Eliminating $h_k$ we derive the recurrence relation $r_k^2 = {\frac{1}{4(1-r_{k-1}^2)}}$, and, solving (knowing $r_1 = 1/2$), we get: $$r_k = \sqrt{\frac{k}{2k+2}}. $$

In particular, this sequence is monotonic increasing in $k$; so every $k$-simplex of maximal radius is acute, and therefore regular.

Now, to complete the theorem: the minimal enclosing ball $B$ of a finite set $S$ is the M.E.B. of the points in $S$ lying on $B$, and therefore the M.E.B. of some simplex with vertices in $S$; and the further generalisation to compact sets is straightforward.

share|improve this answer

If $k=1$, then $r=\frac d2$ is clear.

If $k=2$, then $r\le \frac{\sqrt 3}2 d$.

In general, it seems obvious that the worst case is a simplex. I don't have the asymptotic formula at hand, but I suppose that $\sup \frac rd$ tends to $1$ as $k\to \infty$.

share|improve this answer
1  
If it’s true that the worst case is a simplex then asymptotically (as $k\rightarrow\infty$) the upper bound is $d/\sqrt{2}$. But how to prove that a simplex really is the worst case? –  Robin Houston Nov 19 '12 at 12:57
    
I think that you intend $\frac{\sqrt 3}3$. –  carlop Nov 19 '12 at 13:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.