Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Polytope volume computation

Author: Jim Lawrence
Journal: Math. Comp. 57 (1991), 259-271
MSC: Primary 52B55
MathSciNet review: 1079024
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A combinatorial form of Gram’s relation for convex polytopes can be adapted for use in computing polytope volume. We present an algorithm for volume computation based on this observation. This algorithm is useful in finding the volume of a polytope given as the solution set of a system of linear inequalities, $P = \{ x \in {\mathbb {R}^n}:Ax \leq b\}$ . As an illustration we compute a formula for the volume of a projective image of the n-cube. From this formula we deduce that, when A and b have rational entries (so that the volume of P is also a rational number), the number of binary digits in the denominator of the volume cannot be bounded by a polynomial in the total number of digits in the numerators and denominators of entries of A and b . This settles a question posed by Dyer and Frieze.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 52B55

Retrieve articles in all journals with MSC: 52B55

Additional Information

Article copyright: © Copyright 1991 American Mathematical Society