Inscribed hypersphere of a simplex

Question

What is the formula to calculate the radius $r$ and center $x$ of the inscribed hypersphere from the $n+1$ vertices of an arbitrary simplex in $R^n$? A matrix based solution is preferred.

Answer 1

Given vertices $v_0,\ldots, v_n$, let $$ \begin{pmatrix} \colon\colon & w_0^T & \colon\colon & d_0 \\ \colon\colon & w_1^T & \colon\colon & d_1 \\ & \vdots & & \vdots \\ \colon\colon & w_n^T & \colon\colon & d_n \\ \end{pmatrix} = \begin{pmatrix} \colon\colon & \colon\colon & & \colon\colon \\ v_0 & v_1 & \cdots & v_n \\ \colon\colon & \colon\colon & & \colon\colon \\ 1 & 1 & \cdots & 1 \end{pmatrix}^{-1} $$ with $w_i\in\mathbb{R}^n$ and $d_i\in\mathbb{R}$.

We show that $$ r=\frac{1}{\sum\limits_{i=0}^{n} \left\|w_i\right\|_2} $$ and $$ x=\frac{\sum\limits_{i=0}^{n} \left\|w_i\right\|_2\,v_i}{\sum\limits_{i=0}^{n} \left\|w_i\right\|_2} $$ From the definition of the $w_i$, we can see that $w_j^Tx + d_j=0$ is the equation for the hyperplane that contains all vertices of the simplex except $v_j$. Furthermore, we have $w_j^Tv_j = 1-d_j$.

We must now verify that $x$ has distance $r$ from that hyperplane, i.e. we must verify that $$ w_j^Tx+d_j=r\,\|w_j\|_2\;\;\forall\;j\in\{0,\ldots,n\} $$ We find $$ w_j^Tx+d_j = w_j^T\frac{\sum\limits_{i=0}^{n} \left\|w_i\right\|_2\,v_i}{\sum\limits_{i=0}^{n} \left\|w_i\right\|_2} + d_j= \frac{\sum\limits_{i=0}^{n} \left\|w_i\right\|_2\,w_j^Tv_i}{\sum\limits_{i=0}^{n} \left\|w_i\right\|_2} +d_j \\ =\frac{\sum\limits_{i\neq j} \left\|w_i\right\|_2\,w_j^Tv_i \;+\; \left\|w_j\right\|_2\,w_j^Tv_j}{\sum\limits_{i=0}^{n} \left\|w_i\right\|_2} +d_j \\ =\frac{-\,\sum\limits_{i\neq j} \left\|w_i\right\|_2\,d_j \;+\; \left\|w_j\right\|_2\,(1-d_j)}{\sum\limits_{i=0}^{n} \left\|w_i\right\|_2} +d_j \\ =\frac{-\,\sum\limits_{i=0}^{n} \left\|w_i\right\|_2\,d_j \;+\; \left\|w_j\right\|_2}{\sum\limits_{i=0}^{n} \left\|w_i\right\|_2} +d_j \\ =-d_j \;+\; \frac{ \left\|w_j\right\|_2}{\sum\limits_{i=0}^{n} \left\|w_i\right\|_2} +d_j \\ = r\,\|w_j\|_2 $$ We can see that we are on the correct side of each of the hyperplanes, because $x$ is a convex combination of the $v_i$.

In order to generalize this for $k$-simplices, we need some conditions to enforce that our vectors $w_i$ are in the same subspace as the differences $v_{j_1}-v_{j_2}$. We can achieve this e.g. by choosing $n-k$ vectors $a_1,\ldots,a_{n-k}$ which are perpendicular to the subspace that contains all the differences $v_{j_1}-v_{j_2}$, and then ensure that the $w_i$ are perpendicular to the $a_i$: $$ \begin{pmatrix} \colon\colon & w_0^T & \colon\colon & d_0 \\ & \vdots & & \vdots \\ \colon\colon & w_k^T & \colon\colon & d_k \\ \colon\colon & b_1^T & \colon\colon & c_1 \\ & \vdots & & \vdots \\ \colon\colon & b_{n-k}^T & \colon\colon & c_{n-k} \\ \end{pmatrix} = \begin{pmatrix} \colon\colon & & \colon\colon & \colon\colon & & \colon\colon \\ v_0 & \cdots & v_k & a_1 & \cdots & a_{n-k} \\ \colon\colon & & \colon\colon & \colon\colon & & \colon\colon \\ 1 & \cdots & 1 & 0 & \cdots & 0 \end{pmatrix}^{-1} $$ The radius and centre still are $$ r=\frac{1}{\sum\limits_{i=0}^{k} \left\|w_i\right\|_2} $$ and $$ x=\frac{\sum\limits_{i=0}^{k} \left\|w_i\right\|_2\,v_i}{\sum\limits_{i=0}^{k} \left\|w_i\right\|_2} $$ In practice, the vectors $a_i$ would not be actually computed. Instead, we can use the $QR$-decomposition to obtain the results: $$ QR=Q\begin{pmatrix} R_1 \\ 0 \end{pmatrix} =\begin{pmatrix} Q_1 & Q_2 \end{pmatrix}\begin{pmatrix} R_1 \\ 0 \end{pmatrix} =\begin{pmatrix} & & \\ v_0-v_k & \cdots & v_{k-1}-v_k \\ & & \end{pmatrix} $$ where $Q_1$ contains the first $k$ columns of $Q$, and $Q_2$ contains the last $n-k$ columns. Then we have $$ \begin{pmatrix} w_0^T \\ \vdots \\ w_{k-1}^T \end{pmatrix} = R_1^{-1}Q_1^T $$ or $$ \begin{pmatrix} & & \\ w_0 & \cdots & w_{k-1} \\ & & \end{pmatrix} = Q_1\left(R_1^{-1}\right)^T $$ and $$ w_k=-\sum\limits_{i=0}^{k-1} w_i $$

Answer 2

Given vertices $v_0, v_1, \dots, v_n$, let $S_i$ for $0 \le i \le n$ be the $(n-1)$-dimensional volume of the face of the simplex opposite $v_i$.

Each face, together with the center $x$, spans a smaller simplex whose base has $(n-1$)-volume $S_i$ and whose height is $r$, so its volume is $\frac1n r S_i$ (by analogy with the formulas $A = \frac12bh$ and $V = \frac13Bh$ in $2$ and $3$ dimensions). These $n+1$ simplices partition the original simplex, and their total volume $\frac1n rS_0 + \frac1n rS_1 + \dots + \frac1n rS_n$ is also the volume $V$ of the original simplex. So we have $$r = \frac{nV}{S_0 + S_1 + \dots + S_n}.$$ This argument also shows that the barycentric coordinates of the incenter $x$ are proportional to $[S_0 : S_1 : \dots : S_n]$, so we can find $x$ by the linear combination $$x= \frac{S_0 v_0 + S_1 v_1 + \dots + S_n v_n}{S_0 + S_1 + \dots + S_n}.$$

It remains to compute the volume $V$ and the $(n-1)$-volumes $S_i$. By an extension of the $2$-dimensional formula, we have $$V = \frac1{n!} \left|\det \begin{bmatrix} 1 & - & v_0 & - \\ 1 & - & v_1 & - \\ \vdots & &\vdots & \\ 1 & - & v_n & - \end{bmatrix} \right|$$ where each row holds $1$ followed by the coordinates of one of the vertices.

For the $S_i$, I have a method that works, but I'm not convinced is the easiest. Given $n$ points $v_1, v_2, \dots, v_n$ in $\mathbb R^n$, we can find a direction $w$ such that $\langle w, v_i - v_1 \rangle = 0$ for $i=2, \dots, n$, by solving a system of linear equations. Then the volume of the simplex spanned by $v_1, v_2, \dots, v_n$ and $v_1 + w$ will be $\frac1n \|w\| S_0$, since the final added direction is perpendicular to the face of the simplex. So we can compute the volume of the simplex by the earlier formula, and then divide by $\frac{\|w\|}{n}$ to get $S_0$.

Repeat for the other faces, excluding a different vertex $v_i$ every time, to compute $S_1, \dots, S_n$.