From: "C. Hillman" 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