# circumcenter of the $n$-simplex

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

• Assuming $v_i$ in general position. You do it inductively starting with 2 being the mid-point and successively add new point and orthogonal directions. Mar 10, 2021 at 9:02
• @user10354138 Do you mean finding the intersection point of orthogonals of two faces (recursively starting from the vertices)? Mar 10, 2021 at 9:10
• No, I mean starting from one face $v_1,\dots,v_k$ and its circumcentre $c_k$, the circumcentre of $v_1,\dots,v_{k+1}$ is $c_{k+1}=c_k+\lambda u_{k+1}$ where $u_{k+1}=\operatorname{proj}_{\operatorname{affinespan}\{v_1,\dots,v_k\}^\perp}(v_{k+1}-v_1)$ is new orthogonal direction that you need to take care of. Mar 10, 2021 at 9:16
• That's alright, but how to find $\lambda$? (Intersection with the same orthogonal stepping from another face came to mind.) Mar 10, 2021 at 9:18
• You find it by solving a quadratic (actually only linear) equation $(v_1-c_{k+1})^2=(v_{k+1}-c_{k+1})^2$. Mar 10, 2021 at 9:19

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.

• Why in the first equation, you have $r^2 = \|v_i - c\|^2 \quad\forall i$? What if some vertices are in the circle but not on the circle? Then, it must be $r^2 \ge \|v_i - c\|^2 \quad\forall i$, right?
– NN2
Mar 10, 2021 at 9:10
• The circumcircle of a simplex always goes through all points. Mar 10, 2021 at 9:13

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

• Note that $q$ is from the "extended Grammian" matrix $\hat{Q}$ so there is an extra entry there Feb 23, 2022 at 15:36
• Also not that this index notation does in fact start from 1 and not zero. It is confusing when you are missing the context of the "extended" M and Q. Feb 23, 2022 at 15:45

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

• Is there a reference for this recursive method? It sounds like it is basically a (maybe) optimal algo for the matrix inversion above? And I mean for general dimensions. Feb 23, 2022 at 17:36
• Nah, just my note here. If it's something of interest to you, I could cast it into a note on arxiv, for example. Feb 23, 2022 at 19:09
• I should note that this is missing the projection and dimension reduction steps which are non-trivial (see math.stackexchange.com/questions/1587319/… for ideas). And it might help to add the addition of superscript notation. The barycentric coordinate $b_k^{d + 1}$ depends on the Cartesian coordinate $c_k ^{d}$ with depends on the barycentric coordinate $b_k^d$ and so on. I have yet to get this to work properly (code) and surprisingly have not yet found any examples of libraries implementing this. Feb 28, 2022 at 23:03
• github.com/nschloe/meshplex implements it. I'm not sure what you mean by projection and dimension reduction steps. Feb 28, 2022 at 23:04
• This is turning into a chat. Let's move this to discord.com/channels/818781969562599434/818781969562599438 Mar 1, 2022 at 11:43

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.

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