circumcenter of the $n$-simplex

Question

Given $m$ points $v_i\in\mathbb{R}^n$, $m<n$. How to find the circumcenter of the simplex formed by the points?

Answer 1

In a simplex, the circumcircle goes through all vertices so the distance of the circumcenter $c$ is equal for all vertices $v_i$ of the simplex, $$ r^2 = \|v_i - c\|^2 \quad\forall i. $$ $r$ is the circumradius. Writing the circumcenter in barycentric coordinates, $$ c = \sum_i v_j \alpha_j, \quad \sum\alpha_j = 1, $$ this can be expanded to $$ 2 V^T V \alpha + \left(r^2 - \alpha^T V^TV \alpha\right) = w $$ with $V$ being the colum-matrix of the $v_i$ and $w_i=\|v_i\|^2$.

Calling $\lambda = r^2 - \alpha^T V^TV \alpha$, this can be written as a Lagrangian system $$ \begin{pmatrix} 2V^T V & e\\ e^T & 0 \end{pmatrix} \begin{pmatrix} \alpha\\ \lambda \end{pmatrix} = \begin{pmatrix} w\\ 1 \end{pmatrix} $$ with $e = (1,\dots,1)^T$. Note that $V^T V$ is singular if the spatial dimension is smaller than the number of vertices, e.g., triangles in 2D space. (Quite the typical case really.)

I checked numerically and indeed, $\alpha=(0.5, 0.5)$ if two points are given. I would have hoped that for simple cases like this, this expression simplifies, too, but unfortunately I don't see it.

Answer 2

In Miroslav Fiedler's lovely book Matrices and Graphs in Geometry, he shows how one can use the Cayley-Menger matrix,

$$\mathbf M=\begin{pmatrix} 0&1&1&\cdots&1\\ 1&0&d_{1,2}^2&\cdots&d_{1,n+1}^2\\ 1&d_{2,1}^2&\ddots&&\vdots\\ \vdots&\vdots&&\ddots&d_{n,n+1}^2\\ 1&d_{n+1,1}^2&\cdots&d_{n+1,n}^2&0\end{pmatrix}$$

to determine the circumsphere of an $n$-simplex determined by $n+1$ $n$-dimensional points. Here, $d_{j,k}$ signifies the distance between vertices $v_j$ and $v_k$. Using the formulae from this page, and letting $\mathbf Q=-2\mathbf M^{-1}$, the circumcenter is given by

$$\left(\frac{q_{1,2}}{q_{1,2}+\cdots+q_{1,n+2}}v_1,\cdots,\frac{q_{1,n+2}}{q_{1,2}+\cdots+q_{1,n+2}}v_{n+1}\right)$$

and the circumradius is given by $\dfrac{\sqrt{q_{11}}}{2}$. The book also discusses how to use the Cayley-Menger matrix to get the insphere. (I wrote up a Mathematica implementation of Fiedler's formulae here.)

Answer 3

Let us first focus on one face of the cell and assume that we know the circumcenter $c$ and the normal $u$ pointing towards the opposing vertex. Then the circumcenter of the cell $C$ is $$ C = c + \lambda u $$ for some $\lambda$. Of course $C$ must have the same distance $R$ to all vertices $v_i$ of the cell, $$ \begin{split} R^2 &= \|v_i - (c + \lambda u)\|^2 \quad\forall i,\\ &= \|v_i - c\|^2 + \lambda^2 - 2 \langle v_i - c, u\rangle \lambda \quad\forall i. \end{split} $$ Since $u$ is orthonormal on the face, the last term disappears for all vertices on the face. The first is the circumradius $r$ of the face, so $$ \lambda^2 = R^2 - r^2. $$ For the opposing vertex $v_o$, the term $\langle v_i - c, u\rangle$ really is the altitude $h$ of $v_o$ over the face, so $$ \lambda^2 - 2 h \lambda + \|v_o - c\|^2 = R^2. $$ From these two equations, $\lambda$ can be determined to be $$ \lambda = \frac{\|v_o -c\|^2 - r^2}{2h}. $$ This is the elevation of the circumcenter over the face. Note that it is 0 if the distance of the opposing vertex from the circumcenter of the face is exactly the circumradius of the face -- makes sense, says Thales.

This can be done for every face, and we end up with the $n$-linear coordinates $\lambda_k$ of the circumcenter. These can be converted to barycentric coordinates by multiplication with the face area $s_k$, $$ b_k = \frac{\|v_k - c_k\|^2 - r_k^2}{2h_k} s_k $$ or equivalently (because of $V=\frac{1}{n}h_k s_k$) $$ b_k = \frac{\|v_k - c_k\|^2 - r_k^2}{2h_k^2}. $$ (The constant terms $n$ and $V$ can be discarded.)

Hence, the circumcenter of an $n$-simplex is given by the circumcenters and circumradii of all faces, their altitudes, and the distances of the circumcenters to the opposing vertices. This way, the circumcenter can be computed iteratively "from the ground up", i.e., first compute the circumcenters of the edges, then of the triangles etc. Setting the circumradius of a single point to 0 and the circumcenter to that point, the barycentric coordinates of an edge circumcenter are indeed $$ b_k = \frac{\|e\|^2 - 0}{2 \|e\|^2} = \frac{1}{2}. $$

Answer 4

the center of the circum-sphere of a simplex can be trivially calculated as the solution of a sytem of linear of equations: calculate any spanning tree of the corners and take the intersection of the hyperplanes that contain the midpoints of the tree edges and are orthogonal to them.

Answer 5

Another approach is to form a tall matrix $A\in\mathbb{R}^{N\times n}$, where each row contains the displacement between unique pairs of vertices and $N=\frac{m(m-1)}{2}$ and a vector $b\in\mathbb{R}^N$ where each element is the half of the corresponding difference between the squared distance of pairs of vertices from the origin. The circumcenter $x\in\mathbb{R}^n$ is simply the least squares solution to this overdetermined system. This approach has the disadvantage of evaluating more terms (a quantity that scaled quadratically witgh the number of vertices), however, it should not present singular matrix problems.

$$ \begin{pmatrix} v_2 - v_1 \\ \vdots \\ v_{m} - v_{m-1} \end{pmatrix} \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix}=\frac{1}{2} \begin{pmatrix} \|v_2\|^2-\|v_1\|^2\\ \vdots\\ \|v_m\|^2-\|v_{m-1}\|^2 \end{pmatrix} $$