2 ALGORITHMS FOR DETERMINING VOLUMES OF CONVEX POLYHEDRA

Determining volumes of convex n-dimensional polyhedra defined by a linear system of inequalities is useful in program analysis Two methods for computing these volumes are proposed (1) summing the volumes of stmphces which form the polyhedron, and (2) summing the volumes of (increasingly smaller) paralleleplpeds which can be fit into the polyhedron Assuming that roundoff errors are small, the first method is analytically exact whereas the second one converges to the exact solution at the expense of addmonal computer time Examples of polyhedra whose volumes were computed by programs representing the algorithms are also provided. © 1979, ACM. All rights reserved.