From: Jeff Erickson <jeffe@cs.duke.edu>
Newsgroups: sci.math.research
Subject: Re: volume of polyhedra
Date: Tue, 25 Feb 1997 15:14:52 -0500

gorges wrote:
> 
>  I need to evaluate the volume of a polydedron in n-dimensional
> Euclidean space,
> the vertices of which lie on a polytope, in terms of the coordinates of
> its vertices.

I assume this means "Compute the volume of the convex polytope,
specified by its vertex coordinates."

>    * what the analytic formula is, or
>    * where to seek for an analytic formula, or

There is no such formula, even when n=3.  (You can cheat when n=2 by
listing the vertices in order.)  The volume depends on the combinatorial
structure of the polytope.

>    * if there exist a way to identify the simplexes this polyhedron is
>      formed of in order to evaluate the volume in terms of these
>      simplexes, or

This is one version of the classical "convex hull problem".  Several
algorithms are outlined in Ziegler's excellent "Lectures on Polytopes"
(Springer 1995).

>    * if there exists a code for me to integrate in my program, or

Yes.  Lots.  Perhaps the most useful for you is an implimentation by
Bueler, Enge, Fukuda, and Luthi, available from ETH Zurich:

	ftp://ftp.ifor.math.ethz.ch/pub/volume/

In addition to source code, the directory includes a PostScript
description of several algorithms and some experimental results.  Not
surprisingly, they find that different algorithms are more efficient for
different polytopes.

For other examples of convex hull code (which may or may not give you
the volume of the polytope), see either Nina Amenta's "Directory of
Computational Geometry Softwar"e, at the Geometry Center:

	http://www.geom.umn.edu/locate/cglist/ch.html

or my own page of computational geometry software:

	http://www.cs.duke.edu/~jeffe/compgeom/code.html#hulls

>    * any advise at all.

Good luck!
--
Jeff Erickson                         Center for Geometric Computing
jeffe@cs.duke.edu			             Duke University
http://www.cs.duke.edu/~jeffe