# Relationship between diameter and radius of a point set

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?

-
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

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.

-

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$.

-
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