From: Jeff Erickson 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