From: "C. Hillman" <optimist@u.washington.edu>
Newsgroups: sci.math
Subject: Re: finding volume of tetrahedron with one vertex at origin
Date: 14 Jan 1997 12:57:19 GMT

In article <32DAA78E.7078@qlink.queensu.ca>,
Paul Turkstra <6pt@qlink.queensu.ca> writes:

|> How do I find the volume of a tetrahedron with vertices at the origin,
|> (1,2,0), (0,1,3) and (1,1,1) using determinants and the like?

From  a submission which apparently never made it into the FAQ for this
newsgroup:

THE VOLUME OF SIMPLICES

Simplices (plural of ``simplex'') are convex bodies which generalize
the notions of triangles and tetrahedra to n-dimensional euclidean space,
E^n.  A k-dimensional simplex has k+1 (affinely independent) vertices,
(k+1)k/2! edges, (k+1)k(k-1)/3! two dimensional faces, and so forth up to
k+1 (k-1)-dimensional faces.  Just as triangles can exist in E^3,
k-simplices can exist in E^n for any n >= k.

Any convex polytope (the generalization of polygons and polyhedra to E^n)
can be partitioned into simplices (just as any convex polygon can be
partitioned into triangles), so in principle if you can compute the volume
of arbitrary simplices, you can compute the volume of any convex polytope.

There are several pretty and easily implemented formulae which give
the volume of a k-dimensional simplex sitting in euclidean n-space, S,
in terms of different kinds of given information, such as the coordinates
of the vertices  or the lengths of the edges.  These formulae can be used
by anyone who knows how to compute a determinant, although software such
as Mathematica will probably be needed to evaluate really large
determinants.

I will write Vol_k for ``k-dimensional volume'' (really k-dimensional
Lebesgue measure, for those who know what this means); thus Vol_1 means
length, Vol_2 means area, and so forth.  Unless stated otherwise, S
will denote a k-dimensional simplex in E^n, where n \geq k.
Vol_k(S) will mean the k-dimensional volume of S.
A hyperplane in E^n is an (n-1)-dimensional plane.


1. COMPUTING THE VOLUME OF A SIMPLEX WITH KNOWN VERTICES.

Let S have vertices given by the n-dimensional row vectors v_0, v_1, ... v_k.
Let w_1 = v_1 - v_0, w_2 = v_2 - v_0, ... w_k = v_k - v_0
and let W be the k by n matrix whose rows are the row vectors w_j,
1 \leq j \leq k.  Then the GRAM DETERMINANT FORMULA says

                            | det W W^t |^{1/2}
                Vol_k (S) = ------------------
                                    k!

where W^t is the transpose of W.  Note that W W^t is a k by k matrix,
so this formula makes sense.


2. COMPUTING THE VOLUME OF A SIMPLEX WITH KNOWN EDGE LENGTHS.

Let v_0, v_1, ... v_k be the (unknown) vertices of S and suppose
that || v_i - v_j || = d_{ij} is known.  Let D be the k+2 by k+2 matrix

                    |  0     1         1       ....    1     |
                    |  1     0      d_{01}^2   .... d_{0k}^2 |
                D = | ...             ....     ....   ....   |
                    |  1  d_{k0}^2  d_{k1}^2   ....    0     |

Then the CAYLEY-MENGER DETERMINANT FORMULA says

                              | det D |^{1/2}
                   Vol_k(S) = ---------------
                                 2^{k/2} k!

This generalizes the HERON FORMULA for the area of a triangle in terms of its
edge lengths.


3. COMPUTING THE VOLUME OF A SIMPLEX WITH KNOWN HYPERFACES.

Let S be the n-simplex in E^n whose faces are the n+1 hyperplanes
whose Cartesian equations are given by
         a_{i0} + a_{i1} x_1 + a_{i2} x_2 + ... a_{in} x_n = 0
where 0 <= i <= n.  Note that the x_j are variables standing for real
numbers and the a_{ij} are real constants.
Let A be the n+1 by n+1 matrix with elements a_{ij} and let A_{i0} be the
cofactor matrix of A with respect to a_{i0}.  Then the
KLEBANER-SUDBURY-WATTERSON DETERMINANT FORMULA says

                                    | det A |^n                
           Vol_n (S) = ---------------------------------------
                       n! det A_{00} det A_{10} ... det A_{n0}

Note this is valid only for an n-simplex in E^n.


REFERENCE:

See the paper by Peter Gritzmann and Victor Klee, ``On the complexity of some
basic problems in computational convexity II: Volume and mixed volumes'',
in the book

   Polytopes : abstract, convex, and computational,
   edited by T.  Bisztriczky.
   Boston: Kluwer Academic, 1994.

This is a state of the art survey paper discussing the general problem of the
efficient computation of volume of convex bodies in E^n, and discusses such
fundamental topics as the Brunn-Minkowski theory of mixed volume (a sort of
average of the volume of several bodies) the volume of Minkowski sums of
polytopes, and efficient dissection into simplices, among other things.
The Gram, Cayley-Menger, and KSW formulae are discussed in sections 3.6.1,
3.6.2, and 3.6.3 respectively of this paper.

Chris Hillman