The well-known compass and straight-edge construction of the circum-centre and in-centre of a plane-triangle, including the corresponding radii, generalizes to n-dimensional space. In the n-dimensional space, we are given a set of (n + 1) linearly-independent points. We want to find the centres of their circum-scribed and inscribed spheres, including the corresponding radii. We provide a brief background in Linear Algebra.
A line through the point P, in the direction v, is the radius-vector R, as a function of the parameter t.
R = P + v t.
The vector v need not be; but, sometimes, is normalized.
Theorem: Two lines are the same iff (= if and only if) v2 is a scalar multiple of each v1 and (P2 - P1) also is a scalar multiple of v1.
Since, a straight-line in n-dimensional space is of dimension one, a straight-line may be considered as the null-space of a hyper-plane.
Indeed, this straight-line is the defining normal to the hyper-plane.
A hyper-plane in n-dimensional space is an (n - 1)-dimensional sub-space. A hyper-plane, with unit normal n, is the locus of the radius-vector R, given by the equation
(R - P) . n = 0,
where P is any given point on the hyper-plane. The vector n need not be; but, usually, is normalized.
Theorem: Two planes are the same iff n2 is a scalar multiple of n1 and (P2 - P1) . n1 = 0. Alternatively, the plane may be written
as
R . n = P . n.
Since a hyper-plane in n-dimensional space is of dimension (n - 1), a hyper-plane may be considered as the null space of a straight-line. Indeed, straight-line is the defining normal to the hyper-plane.
The (left or right -- they are the same) product of a vector by a scalar is a new vector, each of whose components has been multiplied by that scalar.
The inner (dot) product a.b is defined as the weighted Lebesque-Stieltjes integral of a times the Hermitian transpose of b, over the given domain.
Of the many possible norms, we employ the one that follows naturally from the inner product. The norm of a is defined as the principal square-root of the inner product of a by itself. Since a.a obviously is real and positive, the norm is positive. In symbols, we write
|| a || = sqrt(a . a).
A vector is said to be normalized, if its norm is one.
A vector may be normalized by the scalar multiplication of the vector by the reciprocal of its norm. In symbols, we write
normalized a = a / || a || = a / sqrt(a . a).
Given a denumerable set {a[n]}of n vectors. We would like to have a set of orthonormal vectors.
The in-situ Gramm-Schmidt orthonormalization algorithms consists of two nested loops.
complex u; real v; int i, j;
For(i = 0; i < n; i++) {
For(j = 0; j < i; j++) {
u = a[i] . a[j]; a[j]-= u a[i]; };
v = sqrt(a[i] . a[i]); a[i]*= 1.0 / v; };
return; };
It is obvious that the resulting vectors each have a unit norm and that they have a pair-wise inner-product equal to zero.
In three-dimensional space, the cross-product provides a perpendicular to a plane. It is easier to compute than the Gramm-Schmidt algorithm. However, the use of the cross-product is a bad habit; because, the cross-product does not generalize readily to higher-dimensional spaces.
Only the last iteration of the outer-loop of the Gramm-Schmidt orthonormalization algorithm is required. That is, i = n - 1. Namely:
complex u; real v; int j;
For(j = 0; j < n - 1; j++) {
u = a[n - 1] . a[j]; a[j]-= u a[i]; };
v = sqrt(a[n - 1] . a[n - 1]); a[n - 1]*= 1.0 / v;
return; };
The distance between a point and a hyper-plane is measured as the projection of a vector between the given point and any arbitrary point on the hyper-plane upon the unit normal to the hyper-plane.
In general, lines do not intersect, unless they explicitly are constructed to do so. Hyper-planes, however, do intersect, unless they are dependent. Thus, a set of n linearly-independent hyper-planes intersect in a unique point. Since a hyper-plane is a linear-equation, all that is required is the inversion of the matrix. We may write this set of n planes as
R . a1 = P1 . a1
R . a2 = P2 . a2
R . a3 = P3 . a3
........................
R . an = Pn . an.
We have employed the symbol a for the defining unit-norm, instead of n; because, a vector n would be confusing with its subscript n. On the left-hand side, the a1 through an constitute a matrix. On the right-hand side, we have a vector. Right-multiply each side of this equation by the inverse of the matrix, to obtain the point of intersection R. The best matrix-inversion algorithm -- the Gaussian elimination -- was known to the Chinese, since before their written history. This algorithm requires exactly n^3 multiplications. There are many other excellent algorithms for the inversion of a matrix. They take slightly more multiplication; but, within three times that required by the Gaussian elimination algorithm. Each algorithm for the inversion of a matrix optionally may provide the determinant of the matrix, at little extra effort.
Since the Kramer method requires the computation of (n + 1) determinants, at best, the Kramer method will require O(n^4) multiplications. Thus, the Kramer method is much slower than the other algorithms for the inversion of a matrix. The advantage of the Kramer method is that it makes clear that the necessary and sufficient condition for the existence of the inverse of a matrix is that its determinant not be zero.
In two-dimensional space, a hyper-plane is difficult to distinguish from a straight-line. The distinguishing feature is that of intersection.
It takes one more point than the dimensionality of the space, to determine a hyper-polyhedron with the fewest vertices. Thus, we consider
the (n + 1) vertices A, B, C, ... in n-dimensional space.
In n-dimensional space, it takes n points to determine a hyper-plane. There are (n + 1) combinations of (n + 1) things, taken n at a
time. Thus, this hyper-polyhedron has (n + 1) faces. For definiteness, we will take the defining unit-normal to each face as pointing
outwards.
Now, we will employ a generalization of the classical compass and straight-edge constructions.
The vertices of the aforementioned hyper-polyhedron determine a unique hyper-sphere, which circumscribes them.
Each vertex must be at the same distance -- the radius -- from the center R of this sphere. Thus,
(R - A)^2 = (R - B)^2.
Expand, to obtain
R^2 - 2 R . A + A^2 = R^2 - 2 R . B + B^2.
Transpose the left-side to the right-side, to obtain
0 = 2 R . (A - B) - (A^2 - B^2) = 2 R . (A - B) - (A + B) . (A - B) = (2 R - (A + B)) . (A - B).
This is a linear equation in R.
Geometrically, this equation states that R lies on the perpendicular bisector of the segment AB.
Write the set of n independent simultaneous equations:
0 = (2 R - (A + B)) . (A - B)
0 = (2 R - (B + C)) . (B - C)
0 = (2 R - (C + D)) . (C - D)
............................................
Invert the matrix and solve for R, the center of the circumscribing hyper-sphere.
Then, the radius of this sphere is
sqrt((R - A)^2).
This algorithms is just the classical straight-edge and compass constructions for the circumscribed circle of a triangle. There is nothing
more. Furthermore, since there is little other than matrix inversion involved, any other algorithm must be equivalent. And, as is true
usually, this algorithm generalizes to n-dimensional space, without anything new.
The equations say it all. However, let us interpret them.
The algorithm for finding the circum-center begins with the definition: The circum-center has to be equidistant to each of a pair of typical
vertices. This equation, however, formally is quadratic in the radius vector R. We transform it into an equation which is linear in
R. The interpretation of this new equation is that the circum-center lies on the intersection of the hyper-planes, which are the
perpendicular bisectors of the edges. We need a set of n independent simultaneous equations; but, there are edges = (n+1)!/((n-2)! 2!)
combinations of n+1 things -- vertices -- taken 2 at a time. And, there are pairs = edges!/((edges-2)! 2!) combinations of edges things taken
2 at a time. So, make a circuit, which visits each vertex exactly once. Do not close the circuit. At each vertex, except the first and
last, take the pair of edges. Now, invert this matrix, to find the center -- called the circum-center -- of the circumscribing hyper-sphere.
This is the classical construction.
The faces of the aforementioned hyper-polyhedron determine a unique hyper-sphere, which is inscribed within them.
Each face must be at the same distance -- the radius -- from the centre R of this sphere.
For a typical pair of the faces, we have
(P - R) . n = (Q - R) . m,
where P is a fixed point in and n is the outward-pointing unit normal to one of these faces, and Q and m for the other face.
Transpose this equation, to obtain
0 = - (P - R) . n + (Q - R) . m = R . (n - m) - (P . n - Q . m).
This is a linear equation in R.
Write the set of n independent simultaneous equations.
Invert the matrix and solve for R, the center of the inscribing hyper-sphere.
Then, the radius of this sphere is
sqrt((R - A)^2).
This algorithms is just the classical straight-edge and compass constructions for the inscribed circle of a triangle. There is nothing
more. Furthermore, since there is little other than matrix inversion involved, any other algorithm must be equivalent. And, as is true
usually, this algorithm generalizes to n-dimensional space, without anything new.
The equations say it all. However, let us interpret them.
The algorithm for finding the in-center begins with the definition: The in-center has to be equidistant to each of the typical pair of
faces, where each face is a hyper-plane. Thus, each face may be designated uniquely by the vertex which it does not contain. We need a
set of n independent simultaneous equations. Again, there is an overabundance of candidates. So, make a circuit, which visits each vertex
exactly once. Do not close the circuit. At each vertex, except the first and last, take the pair of faces. Now, invert this matrix, to
find the center -- called the in-center -- of the inscribing hyper-sphere.
This is the classical construction.
The distance between the centers of these two spheres -- the circumscribing and inscribing spheres -- is
|| R-circuscribing - R-inscribing || = sqrt((R-circuscribing - R-inscribing)^2).
Webmaster@rism.com Copyright (c) 2000 by R. I. 'Scibor-Marchocki. Last modified Thursday 22-nd June 2000.