volume of a k-simplex...

[Jonathan Shewchuk]

> I got this formula
>
>            | det (W*W^t) | ^(1/2)
> Volume_k = ----------------------
>                     k!
>
> on the site:
> http://www.math.washington.edu/~hillman/PUB/volume
>
> with W the matrix with k rows and n columns
> where W=(v_1-v_0)
>         (v_2-v_0)
>         (  ...  )
>         (v_k-v_0)
>
> with row vectors v_i the k+1 vertices of the
> k-simplex in R^n.
>
> W^t denotes the transpose of W.
>
> Are both formulae equivalent when n=k?

Almost.  When n = k, this formula is equivalent to the formulae William Flis
and Han-Wen Nienhuys gave you--except that this formula always returns a
positive volume, whereas the Flis and Nienhuys formulae gives you orientation
information in the sign of the result (e.g. are the triangle's vertices in
clockwise or counterclockwise order?).

Note that when n = k, W is square, so | det (W*W^t) | ^(1/2) = det(W),
and det(W) is obviously faster to compute than | det (W*W^t) | ^(1/2)
(and gives you the orientation information).  So for the special case n = k,
I recommend using

Volume_k = det(W) / k!

Although the formulae are numerically equivalent up to sign, they are very
different when floating-point roundoff error enters the picture.  The Flis
and Nienhuys formulae can have unnecessarily large errors, especially if the
simplex is far from the origin.  The formula on the Washington site (and the
formula det(W) / k! when n = k) is numerically much better behaved.  (If you
care to know why, download my "Lecture Notes on Geometric Robustness" from
http://www.cs.berkeley.edu/~jrs/mesh/ under Lecture 13, and read Section 2.)

Jonathan Shewchuk
UC Berkeley


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.