next up previous contents
Next: Voronoi Diagram and Delaunay Up: Convex Polyhedron Previous: Is there any efficient   Contents

Is there any efficient algorithm to compute the volume of a convex polytope in $ R^d$?

It is known that computing the volume of a $ V$-polytope (or H-polytope) is #P-hard, see [DF88] and [Kha93]. There are theoretically efficient randomized algorithms to approximate the volume of a convex body [LS93] but no implementation seems to be available.

There is a comparative study [BEF00] of various volume computation algorithms for convex polytopes. It indicates that there is no single algorithm that works well for many different types of polytopes. For ``near'' simple polytopes, triangulation-based algorithms are more efficient. For ``near'' simplicial polytopes, sign-decomposition-based algorithms are better. See the paper for the justification of these claims.

Komei Fukuda 2004-08-26