A formula
for the Ncircumsphere of an Nsimplex .
G.Westendorp
april 2013
We show
that the circumradius and circumcentre of the Ncircumsphere
of an Nsimplex
are obtained directly from elements of the inverse (CM^{1})
of the Cayley Menger
matrix (CM^{ }) for
the Nsimplex.
In 3
dimensions, if:
_{}
Then (α, β, γ,
δ) are the 4
barycentric coordinates of the circumcentre and r is
the circumradius. This generalises to Ndimensions in
a straightforward manner.
Our formula
provides a compact expression for the circumcentre and circumradius
that it is
coordinate independent in the sense that it requires only the squared
distances
between the vertices. We will use the conformal model of geometric
algebra for
the proof, but the equation itself uses only the CayleyMenger matrix.
An Ncircumsphere
is an Ndimensional sphere,
that passes through the (N+1)
points of an Nsimplex.
In 2 dimensions, it is most easily visualised and corresponds to the
circumcircle.
The
circumcircle of a triangle,
with the barycentric coordinates (α, β, γ)
of the circumcentre shown as areas of 3 subtriangles,
opposite to the vertices (A,B,C) respectively.
_{}

Eq 1

(x,y,z)=
α(x_{A},y_{A},z_{A}) + β(x_{B},y_{B},z_{B}) + γ (x_{C},y_{C},z_{C}) + δ (x_{D},y_{D},z_{D})

Eq 2

To prove
this, we will use the machinery of conformal
geometric algebra. We refer to [1] for an explanation of the
terminology
and principles of conformal geometric algebra. An important reason it
is useful
for our problem, is that the internal product of 2 points in the
conformal
model is equal to 1/2 times the squared distance between the
corresponding Euclidean
points. Using this fact we can see that the CayleyMenger matrix is 2
times to
the Grammian matrix of the 4 points (A,B,C,D)
of the tetrahedron, together with minus half the ‘point at
infinity’ (n_{∞}/2):
_{}

Eq 3

Next, we
use another nice feature of conformal geometric algebra, that a sphere (X) through points (A,B,C,D)
is given by the exterior product of these points:
X=A^B^C^D
(ie. the sphere is the set of
points (p) that satisfy p ^ X
= 0)
The circumcentre
and circumradius can be found by computing the Hodge dual of X* of X. The Hodge dual of a sphere with
radius (r) and centre (_{}) has the
form:
_{}

Eq 4

So from the
Hodge dual, we can read of the centre as the Euclidean part, and then
use the (n_{∞}) component to obtain r^{2}
The
computation of X* uses the
contraction (_{┘}) with
the pseudoscalar and the expansion of a
point P in into its Euclidean part and the
extra dimensions (n_{o}) and
(n_{∞}):
_{}
The determinant terms
in the above expansion of the X^{*}
correspond to the cofactor expansion for the inverse
of top row of CM, so we can replace
these determinant terms with the coefficients from Eq 1:
_{}
(Eq 5)
Comparing the
Euclidean parts of equations 4 and 5, we find the expression for the
centre (_{}):
_{}

Eq 6

We can
verify that the n_{0}
components of equation 5 add to 1 by noting that:
_{}
To justify
that we labelled element (1,1) of CM^{1 }as 2r^{2},
we first check that if the circumcentre is at the origin, then the n_{∞ }component of X^{*}
according to Eq 5:
This is
indeed the correct value for the dual a circumsphere at the origin.
(We used _{}.)
So our
expression for CM^{1}_{(1,1) }is valid if the sphere is at the
origin. But the
elements of the CayleyMenger matrix are invariant under translations,
and so
is the circumradius, therefore the element (1,1)
must
remain equal to 2r^{2}.
Finally, we
mention an interpretation of the other terms (Y_{ij}) in equation 1.
The original motivation for this work was in fact to find an expression
for
resistance values in terms of squared lengths for Nsimplexes
that discretise a conducting
medium. As we discuss in another webpage,
Y_{ij} =1/R_{ij}
, where
R_{ij}
is the effective resistance value between vertices i and j of the Nsimplex.
(Assuming unit specific conductivity of the medium)
Illustration
for the interpretation of Y_{ij}
=1/R_{ij} as the effective conductance
values for simplicial discretisation
using electric circuits.
Appendix: A proof adapted from a 1930 article by Coxeter.
Max Goering brought a 1930 article by Coxeter
[2] to my attention. Coxeter does not
actually
mention the Cayley menger
matrix or its inverse, but from his article I was able to construct the
following proof, requiring no conformal geometric algebra. We will show
that the Ndimensional sphere
containing all (N+1) points of
an Nsimplex, is found directly from the inverse of the Cayley
Menger matrix of the simplex.
In an (N+1)
dimensional Euclidean space, let X_{i} be (N+1) linearly independent
vectors. A point (P) may be
expressed using Einstein summation convention as:
P = x_{i}X_{i}_{}
The X_{i
}also define the vertices of an Nsimplex
embedded in (N+1)dimensional space.
The condition, Σx_{i}
= 1 defines an Ndimensional subspace, embedded in N+1 dimensions. The x_{i }are
“barycentric coordinates” of this Ndimensional
subspace, they are weights
such that a coordinate in the Ndimensional
space is the weighted sum of the vertices of the Nsimplex.
The set of
conditions
0 <= x_{i
}<=1
tell us
if a point is inside the simplex. This can be very useful!
Let L^{2}_{ij} be the squared
distance
between 2 vertices (i
and j) of the simplex.
The
distance (PQ) between 2 points (P,Q) with barycentric coordinates (p_{i} and q_{j}) inside the N
simplex is:
2PQ^{2}
= Σ_{ij} (p_{i} q_{j} L^{2}_{ij})
(eq A1)
So ½L^{2}_{ij} is a bit the
metric tensor for barycentric coordinates, except that barycentric
coordinates have one superfluous element.
This is
proved by Coxeter, but it may be quickly
seen by
noting that
it is obviously true for any 2 vertices themselves. (The factor 2
arises
because the distance occurs twice in the symmetric sum) But the squared
length
must be linear in the coefficients p_{i}
and q_{j},
so expression (A1) must be true.
Now let us
find the circumsphere, barycentric coordinates (x_{i})
and radius (R).
The
condition may be written:
_{}
The top
line of the matrix multiplication expresses Σx_{i} = 1. The
other lines express the condition,
using (A1), that the distance between
the
circumcentre and a vertex is R^{2}.
We
recognise the matrix in the above expression as the Cayley
Menger matrix (CM),
whose determinant is used to compute the Nvolume
of a simplex.
Now, by
using the inverse CM^{1}
we find our result directly:
_{}
> CM^{1}_{11} = 2R^{2}
x_{j} = CM^{1}_{1(j+1)}
_{ }
References:
1. Dorst, L. et al (2007), Geometric Algebra for
Computer
Science, MorganKaufmann. ISBN 0123749425
2. The
Circumradius of the General Simplex, H. S. M. Coxeter,
The Mathematical Gazette, Vol. 15, No. 210
(Dec.,
1930), pp. 229231