Relation between radius of smallest sphere containing a n-dimensional simplex and its edge length

Question

I have a $n$-dimensional simplex with maximum edge length equal to $l$. Do we have a relationship between radius of minimum volume sphere (thus minimum radius sphere) containing the simplex and maximum edge length "$l$". Also is there a relationship between volume of the simplex and volume of minimum sphere (in terms of radius) containing it.

Answer 1

Yes, one can bound the radius of the minimal enclosing sphere by the largest edge length.

For any $n \ge 1$ and $n$-simplex $S \subset \mathbb{R}^n$ with vertices $v_1, \ldots, v_{n+1}$. Let

• $\ell_{ij} = \| v_i - v_j \|$ be the edge lengths.
• $\ell_{\rm max} = \max\limits_{i<j} \ell_{ij}$ be the longest edge length.
• $\bar{B}(c,r) = \{ v \in \mathbb{R}^n : \| v - c \| \le r \}$ be the closed ball centered at $c \in \mathbb{R}^n$ with radius $r$.
• $r_{\rm min}$ be the smallest $r$ such that there is a $c \in \mathbb{R}^n$ with $S \subset \bar{B}(c,r)$.

We have

$$\bbox[border:1px solid blue;padding: 8px;]{r_{min} \le \sqrt{\frac{n}{2(n+1)}} \ell_{\rm max}}\tag{*1}$$

This is a special case of Jung's theorem.

For any compact set $K \subset \mathbb{R}^n$, let $d = \max_{p,q \in K} \| p - q \|$ be its diameter. Jung's theorem states that one can find a closed ball $\bar{B}(c,r)$ containing $K$ with radius $r \le \sqrt{\frac{n}{2(n+1)}} d$.

Look at here for one way of proving this more general result.

---

TL;DR

For my own benefit of understanding this stuff, following is a proof of $(*1)$.

We will prove $(*1)$ by induction in $n$.

The base case $n = 1$ is trivial. For any $n > 1$, let us assume above statement is true for all dimension $1 \le m < n$.

Let $\varphi_S : \mathbb{R}^n \to \mathbb{R}$ be the function: $\;\;\varphi_{S}(v) = \max\limits_{i} \| v - v_i \|^2$.
Since $S$ is convex, for any closed ball $\bar{B}(c,r)$, we have $$S \subset \bar{B}(c,r) \quad\iff\quad \text{ all }v_i \in \bar{B}(c,r) \quad\iff\quad \text{ all }\| v_i - c \| \le r \quad\iff\quad \varphi_S(c) \le r^2 $$ The problem of finding $r_{min}$ is equivalent to minimizing the function $\varphi_S(v)$.

1. $\varphi_S(v)$ achieve its minimum at some unique $c_{\rm min}$ with $r_{\rm min}^2 = \varphi_S(c_{\rm min})$.

   For each $i$, $\| v - v_i \|^2$ is strictly convex and continuous in $v$. Being pointwise maximum of these sort of functions, $\varphi_S(v)$ is strictly convex and continuous too. Since $\varphi_S(v)$ is bounded from below and blows up as $\| v \| \to \infty$. $\varphi_S(v)$ achieve its absolute minimum at some unique point $c_{\rm min}$.

2. $c_{\rm min} \in S$.

   $S$ is the intersection of $n+1$ closed half spaces supported at their faces. For $v \notin S$, $v$ belongs to at least one of the complement of these closed half space. If one move $v$ towards $S$ along the normal direction of the corresponding face, all $\| v - v_i \|^2$ will be decreased. As a result, $\varphi_S(v)$ will be decreased and $v$ cannot be $c_{\rm min}$.

3. If $c_{\rm min} \in \partial S$, then $c_{\rm min}$ belongs to some $m$-face $S'$ of $S$ with $m < n$. By induction assumption, we will have $$r_{min} \le \sqrt{\frac{m}{2(m+1)}}\ell_{max}(S') < \sqrt{\frac{n}{2(n+1)}}\ell_{max}(S)$$

4. Otherwise, $c_{\rm min} \in {\rm int}\,S$ and $\| c_{\rm min} - v_i \| = r_{\rm min}$ for all $i$.

   Let $I$ be the set of vertices at a distance $r_{\rm min}$ from $c_{\rm min}$. It is clear $I$ contains at least two vertices. If $I$ does not exhaust all vertices, then $c_{\rm min}$ need to belong to the hyperplane span by vertices in $I$. If not, we can reduce $\| v - v_i \|$ for $v_i \in I$ by moving $v$ from $c_{\rm min}$ towards that hyperplane while keeping $\| v - v_j \| < r_{\rm min}$ for those $v \notin I$. This contradicts with the minimality of $c_{\rm min}$. If $c_{\rm min}$ do belong to that hyperplane, it will belong to $\partial S$. This contradicts with the assumption $c_{\rm min} \in {\rm int}\,S$. As a result, $I$ contains all vertices.

   Since $c_{\rm min} \in {\rm int}\,S$, there exists $n+1$ numbers $\lambda_i$ such that $$c_{\rm min} = \sum_{i}\lambda_i v_i \quad\text{ with }\quad\begin{cases} \lambda_1, \ldots, \lambda_{n+1} > 0\\ \sum\limits_{i} \lambda_i = 1 \end{cases}$$

   These are the barycentric coordiantes of $c_{\rm min}$ with respect to simplex $S$.

   Recall for any two points $u, v \in S$ with barycentric coordinates $\mu_i, \nu_i$, their distance is given by following formula: $$\| u - v \|^2 = - \sum_{i<j} \ell_{ij}^2(\mu_i - \nu_i)(\mu_j - \nu_j)$$

   Apply this to $c_{\rm min}$ and vertex $v_k$, we have $$r_{\rm min}^2 = \| c_{\rm min} - v_k\|^2 = -\sum_{i<j}\ell_{ij}^2(\lambda_i - \delta_{ki})(\lambda_j - \delta_{kj}) = \sum_{i\ne k}\ell_{ki}^2\lambda_i - \frac12\sum_{i,j}\ell_{ij}^2\lambda_i\lambda_j$$

   Multiply by $\lambda_k$ and sum over $k$, we obtain $$r_{\rm min}^2 = \frac12\sum_{i,j} \ell_{ij}^2\lambda_i\lambda_j \quad\implies\quad 2 r_{\rm min}^2 = \sum_{i\ne k}\ell_{ki}^2\lambda_i,\;\forall k$$

   Sum over $k$ again, we obtain $$2(n+1)r_{\rm min}^2 = \sum_{k,i}\ell_{k,i}^2\lambda_i \le n\ell_{\rm max}^2\sum_i\lambda_i = n\ell_{\rm max}^2$$

Combine step $3$. and $4$., $(*1)$ is true for this $n$ and by principle of induction, it is true for all $n \ge 1$.

---

Answer 2

Calculations are known for the circumscribed hypersphere,¹ but as achillehui pointed out, this is in general different from the minimum radius enclosing sphere. In the literature, your problem is often called the Minimum Enclosing Ball (MEB) problem. This has been studied extensively for enclosing arbitrary points (rather than just the vertices of a simplex). It is an LP-type problem, and that is how it is usually solved: via linear programming. Below is a reference² that gives background and citations on the problem. Note from this paper that an exact algorithm due to Gärtner is built into CGAL.

---

¹ A formula for the N-circumsphere of an N-simplex, by G.Westendorp.

² Kumar, Piyush, Joseph SB Mitchell, and E. Alper Yildirim. "Comuting Core-Sets and Approximate Smallest Enclosing HyperSpheres in High Dimensions." ALENEX. 2003. (PDF download.)