Polytope volume computation

Author:
Jim Lawrence

Journal:
Math. Comp. **57** (1991), 259-271

MSC:
Primary 52B55

DOI:
https://doi.org/10.1090/S0025-5718-1991-1079024-2

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.

- Eugene L. Allgower and Phillip H. Schmidt,
*Computing volumes of polyhedra*, Math. Comp.**46**(1986), no. 173, 171–174. MR**815838**, DOI https://doi.org/10.1090/S0025-5718-1986-0815838-7 - M. L. Balinski,
*An algorithm for finding all vertices of convex polyhedral sets*, J. Soc. Indust. Appl. Math.**9**(1961), 72–88. MR**142057**
J. Bárány and Z. Füredi, - D. L. Barrow and P. W. Smith,
*Classroom Notes: Spline Notation Applied to a Volume Problem*, Amer. Math. Monthly**86**(1979), no. 1, 50–51. MR**1538918**, DOI https://doi.org/10.2307/2320304 - Jacques Cohen and Timothy Hickey,
*Two algorithms for determining volumes of convex polyhedra*, J. Assoc. Comput. Mach.**26**(1979), no. 3, 401–414. MR**535261**, DOI https://doi.org/10.1145/322139.322141 - M. E. Dyer,
*The complexity of vertex enumeration methods*, Math. Oper. Res.**8**(1983), no. 3, 381–402. MR**716120**, DOI https://doi.org/10.1287/moor.8.3.381 - M. E. Dyer and A. M. Frieze,
*On the complexity of computing the volume of a polyhedron*, SIAM J. Comput.**17**(1988), no. 5, 967–974. MR**961051**, DOI https://doi.org/10.1137/0217060 - H. G. Eggleston,
*Convexity*, Cambridge Tracts in Mathematics and Mathematical Physics, No. 47, Cambridge University Press, New York, 1958. MR**0124813** - G. Elekes,
*A geometric inequality and the complexity of computing volume*, Discrete Comput. Geom.**1**(1986), no. 4, 289–292. MR**866364**, DOI https://doi.org/10.1007/BF02187701 - Saul I. Gass,
*Linear programming*, 4th ed., McGraw-Hill Book Co., New York-Auckland-Düsseldorf, 1975. Methods and applications. MR**0373586**
B. Grünbaum, - G. H. Hardy and E. M. Wright,
*An introduction to the theory of numbers*, 6th ed., Oxford University Press, Oxford, 2008. Revised by D. R. Heath-Brown and J. H. Silverman; With a foreword by Andrew Wiles. MR**2445243** - J. B. Lasserre,
*An analytical expression and an algorithm for the volume of a convex polyhedron in ${\bf R}^{n}$*, J. Optim. Theory Appl.**39**(1983), no. 3, 363–377. MR**703477**, DOI https://doi.org/10.1007/BF00934543 - Jim Lawrence,
*Valuations and polarity*, Discrete Comput. Geom.**3**(1988), no. 4, 307–324. MR**947219**, DOI https://doi.org/10.1007/BF02187915 - Yong Tsui Lee and Aristides A. G. Requicha,
*Algorithms for computing the volume and other integral properties of solids. I. Known methods and open issues*, Comm. ACM**25**(1982), no. 9, 635–641. MR**680293**, DOI https://doi.org/10.1145/358628.358643 - Yong Tsui Lee and Aristides A. G. Requicha,
*Algorithms for computing the volume and other integral properties of solids. I. Known methods and open issues*, Comm. ACM**25**(1982), no. 9, 635–641. MR**680293**, DOI https://doi.org/10.1145/358628.358643 - László Lovász,
*An algorithmic theory of numbers, graphs and convexity*, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 50, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1986. MR**861822** - Peter McMullen,
*Angle-sum relations for polyhedral sets*, Mathematika**33**(1986), no. 2, 173–188 (1987). MR**882490**, DOI https://doi.org/10.1112/S0025579300011165 - P. McMullen and G. C. Shephard,
*Convex polytopes and the upper bound conjecture*, Cambridge University Press, London-New York, 1971. Prepared in collaboration with J. E. Reeve and A. A. Ball; London Mathematical Society Lecture Note Series, 3. MR**0301635** - Miroslav Maňas and Josef Nedoma,
*Finding all vertices of a convex polyhedron*, Numer. Math.**12**(1968), 226–229. MR**235705**, DOI https://doi.org/10.1007/BF02162916 - T. H. Mattheiss,
*An algorithm for determining irrelevant constraints and all verticles in systems of linear inequalities*, Operations Res.**21**(1973), 247–260. Mathematical programming and its applications. MR**437087**, DOI https://doi.org/10.1287/opre.21.1.247 - T. H. Matheiss and David S. Rubin,
*A survey and comparison of methods for finding all vertices of convex polyhedral sets*, Math. Oper. Res.**5**(1980), no. 2, 167–185. MR**571811**, DOI https://doi.org/10.1287/moor.5.2.167
G. C. Rota, - Alexander Schrijver,
*Theory of linear and integer programming*, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR**874114** - G. C. Shephard,
*An elementary proof of Gram’s theorem for convex polytopes*, Canadian J. Math.**19**(1967), 1214–1217. MR**225228**, DOI https://doi.org/10.4153/CJM-1967-110-7
D. P. Shoemaker and T. C. Huang, - Ted Speevak,
*An efficient algorithm for obtaining the volume of a special kind of pyramid and application to convex polyhedra*, Math. Comp.**46**(1986), no. 174, 531–536. MR**829623**, DOI https://doi.org/10.1090/S0025-5718-1986-0829623-3 - Josef Stoer and Christoph Witzgall,
*Convexity and optimization in finite dimensions. I*, Die Grundlehren der mathematischen Wissenschaften, Band 163, Springer-Verlag, New York-Berlin, 1970. MR**0286498** - Leslie G. Valiant,
*The complexity of enumeration and reliability problems*, SIAM J. Comput.**8**(1979), no. 3, 410–421. MR**539258**, DOI https://doi.org/10.1137/0208032 - B. von Hohenbalken,
*Finding simplicial subdivisions of polytopes*, Math. Programming**21**(1981), no. 2, 233–234. MR**623842**, DOI https://doi.org/10.1007/BF01584244

*Computing the volume is difficult*, Proc. 18th Annual ACM Sympos. on Theory of Computing, 1986, pp. 442-447.

*Convex polytopes*, Interscience, 1967.

*The valuation ring*, Studies in Pure Mathematics (L. Mirsky, ed.), Academic Press, New York, 1971.

*A systematic method for calculating volumes of polyhedra corresponding to Brillouin zones*, Acta Cryst. Sect. A

**7**(1954), 249-259.

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