Polytope volume computation
Author:
Jim Lawrence
Journal:
Math. Comp. 57 (1991), 259271
MSC:
Primary 52B55
MathSciNet review:
1079024
Fulltext 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, . As an illustration we compute a formula for the volume of a projective image of the ncube. 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.
 [1]
Eugene
L. Allgower and Phillip
H. Schmidt, Computing volumes of
polyhedra, Math. Comp. 46
(1986), no. 173, 171–174. MR 815838
(87d:51036), http://dx.doi.org/10.1090/S00255718198608158387
 [2]
M.
L. Balinski, An algorithm for finding all vertices of convex
polyhedral sets, J. Soc. Indust. Appl. Math. 9
(1961), 72–88. MR 0142057
(25 #5451)
 [3]
J. Bárány and Z. Füredi, Computing the volume is difficult, Proc. 18th Annual ACM Sympos. on Theory of Computing, 1986, pp. 442447.
 [4]
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, http://dx.doi.org/10.2307/2320304
 [5]
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
(80g:52006), http://dx.doi.org/10.1145/322139.322141
 [6]
M.
E. Dyer, The complexity of vertex enumeration methods, Math.
Oper. Res. 8 (1983), no. 3, 381–402. MR 716120
(85j:68102), http://dx.doi.org/10.1287/moor.8.3.381
 [7]
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 (90f:68077), http://dx.doi.org/10.1137/0217060
 [8]
H.
G. Eggleston, Convexity, Cambridge Tracts in Mathematics and
Mathematical Physics, No. 47, Cambridge University Press, New York, 1958.
MR
0124813 (23 #A2123)
 [9]
G.
Elekes, A geometric inequality and the complexity of computing
volume, Discrete Comput. Geom. 1 (1986), no. 4,
289–292. MR
866364 (87k:68138), http://dx.doi.org/10.1007/BF02187701
 [10]
Saul
I. Gass, Linear programming, 4th ed., McGrawHill Book Co.,
New YorkAucklandDüsseldorf, 1975. Methods and applications. MR 0373586
(51 #9786)
 [11]
B. Grünbaum, Convex polytopes, Interscience, 1967.
 [12]
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. HeathBrown and J.
H. Silverman; With a foreword by Andrew Wiles. MR 2445243
(2009i:11001)
 [13]
J.
B. Lasserre, An analytical expression and an algorithm for the
volume of a convex polyhedron in 𝑅ⁿ, J. Optim. Theory
Appl. 39 (1983), no. 3, 363–377. MR 703477
(84m:52018), http://dx.doi.org/10.1007/BF00934543
 [14]
Jim
Lawrence, Valuations and polarity, Discrete Comput. Geom.
3 (1988), no. 4, 307–324. MR 947219
(90b:52001), http://dx.doi.org/10.1007/BF02187915
 [15]
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
(84a:52003a), http://dx.doi.org/10.1145/358628.358643
 [16]
Yong
Tsui Lee and Aristides
A. G. Requicha, Algorithms for computing the volume and other
integral properties of solids. II. A family of algorithms based on
representation conversion and cellular approxim, Comm. ACM
25 (1982), no. 9, 642–650. MR 680294
(84a:52003b), http://dx.doi.org/10.1145/358628.358648
 [17]
László
Lovász, An algorithmic theory of numbers, graphs and
convexity, CBMSNSF Regional Conference Series in Applied Mathematics,
vol. 50, Society for Industrial and Applied Mathematics (SIAM),
Philadelphia, PA, 1986. MR 861822
(87m:68066)
 [18]
Peter
McMullen, Anglesum relations for polyhedral sets, Mathematika
33 (1986), no. 2, 173–188 (1987). MR 882490
(88f:52009), http://dx.doi.org/10.1112/S0025579300011165
 [19]
P.
McMullen and G.
C. Shephard, Convex polytopes and the upper bound conjecture,
Cambridge University Press, LondonNew York, 1971. Prepared in
collaboration with J. E. Reeve and A. A. Ball; London Mathematical Society
Lecture Note Series, 3. MR 0301635
(46 #791)
 [20]
Miroslav
Maňas and Josef
Nedoma, Finding all vertices of a convex polyhedron, Numer.
Math. 12 (1968), 226–229. MR 0235705
(38 #4008)
 [21]
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
0437087 (55 #10020)
 [22]
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
(81e:90059), http://dx.doi.org/10.1287/moor.5.2.167
 [23]
G. C. Rota, The valuation ring, Studies in Pure Mathematics (L. Mirsky, ed.), Academic Press, New York, 1971.
 [24]
Alexander
Schrijver, Theory of linear and integer programming,
WileyInterscience Series in Discrete Mathematics, John Wiley & Sons,
Ltd., Chichester, 1986. A WileyInterscience Publication. MR 874114
(88m:90090)
 [25]
G.
C. Shephard, An elementary proof of Gram’s theorem for convex
polytopes, Canad. J. Math. 19 (1967),
1214–1217. MR 0225228
(37 #822)
 [26]
D. P. Shoemaker and T. C. Huang, A systematic method for calculating volumes of polyhedra corresponding to Brillouin zones, Acta Cryst. Sect. A 7 (1954), 249259.
 [27]
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
(87d:52012), http://dx.doi.org/10.1090/S00255718198608296233
 [28]
Josef
Stoer and Christoph
Witzgall, Convexity and optimization in finite dimensions. I,
Die Grundlehren der mathematischen Wissenschaften, Band 163,
SpringerVerlag, New YorkBerlin, 1970. MR 0286498
(44 #3707)
 [29]
Leslie
G. Valiant, The complexity of enumeration and reliability
problems, SIAM J. Comput. 8 (1979), no. 3,
410–421. MR
539258 (80f:68055), http://dx.doi.org/10.1137/0208032
 [30]
B.
von Hohenbalken, Finding simplicial subdivisions of polytopes,
Math. Programming 21 (1981), no. 2, 233–234. MR 623842
(82h:52001), http://dx.doi.org/10.1007/BF01584244
 [1]
 E. L. Allgower and P. M. Schmidt, Computing volumes of polyhedra, Math. Comp. 46 (1986), 171174. MR 815838 (87d:51036)
 [2]
 M. L. Balinski, An algorithm for finding all vertices of convex polyhedral sets, SIAM J. Appl. Math. 9 (1961), 7288. MR 0142057 (25:5451)
 [3]
 J. Bárány and Z. Füredi, Computing the volume is difficult, Proc. 18th Annual ACM Sympos. on Theory of Computing, 1986, pp. 442447.
 [4]
 D. L. Barrow and P. W. Smith, Spline notation applied to a volume problem, Amer. Math. Monthly 86 (1979), 5051. MR 1538918
 [5]
 J. Cohen and T. Hickey, Two algorithms for determining volumes of convex polyhedra, J. Assoc. Comput. Mach. 26 (1979), 401414. MR 535261 (80g:52006)
 [6]
 M. E. Dyer, The complexity of vertex enumeration methods, Math. Oper. Res. 8 (1983), 381402. MR 716120 (85j:68102)
 [7]
 M. E. Dyer and A. M. Frieze, On the complexity of computing the volume of a polyhedron, SIAM J. Comput. 17 (1988), 967974. MR 961051 (90f:68077)
 [8]
 H. G. Eggleston, Convexity, Cambridge Univ. Press, 1958. MR 0124813 (23:A2123)
 [9]
 G. Elekes, A geometric inequality and the complexity of computing volume, Discrete Comput. Geom. 1 (1986), 289292. MR 866364 (87k:68138)
 [10]
 S. I. Gass, Linear programming, McGrawHill, 1958. MR 0373586 (51:9786)
 [11]
 B. Grünbaum, Convex polytopes, Interscience, 1967.
 [12]
 G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, fourth ed., Clarendon Press, 1968. MR 2445243 (2009i:11001)
 [13]
 J. B. Lasserre, An analytical expression and an algorithm for the volume of a convex polyhedron in , J. Optim. Theory Appl. 39 (1983), 363377. MR 703477 (84m:52018)
 [14]
 J. Lawrence, Valuations and polarity, Discrete Comput. Geom. 3 (1988), 307324. MR 947219 (90b:52001)
 [15]
 Y. T. Lee and A. A. G. Requicha, Algorithms for computing the volume and other integral properties of solids. I. Known methods and open issues, Comm. ACM 25 (1982), 635641. MR 680293 (84a:52003a)
 [16]
 , Algorithms for computing the volume and other integral properties of solids. II. A family of algorithms based on representation conversion and cellular approximation, Comm. ACM 25 (1982), 642650. MR 680294 (84a:52003b)
 [17]
 L. Lovász, An algorithmic theory of numbers, graphs and convexity, SIAM, 1986. MR 861822 (87m:68066)
 [18]
 P. McMullen, Anglesum relations for polyhedral sets, Mathematika 33 (1986), 173188. MR 882490 (88f:52009)
 [19]
 P. McMullen and G. C. Shephard, Convex polytopes and the upper bound conjecture, Cambridge Univ. Press, 1971. MR 0301635 (46:791)
 [20]
 M. Manas and J. Nedoma, Finding all vertices of a convex polyhedron, Numer. Math. 12 (1968), 226229. MR 0235705 (38:4008)
 [21]
 T. H. Mattheiss, An algorithm for determining irrelevant constraints and all vertices in systems of linear inequalities, Oper. Res. 21 (1973), 247260. MR 0437087 (55:10020)
 [22]
 T. H. Mattheis and D. S. Rubin, A survey and comparison of methods for finding all vertices of convex polyhedral sets, Math. Oper. Res. 5 (1980), 167185. MR 571811 (81e:90059)
 [23]
 G. C. Rota, The valuation ring, Studies in Pure Mathematics (L. Mirsky, ed.), Academic Press, New York, 1971.
 [24]
 A. Schrijver, Theory of linear and integer programming, Wiley, Chichester, 1986. MR 874114 (88m:90090)
 [25]
 G. C. Shephard, An elementary proof of Gram's theorem for convex polytopes, Canad. J. Math. 19 (1967), 12141217. MR 0225228 (37:822)
 [26]
 D. P. Shoemaker and T. C. Huang, A systematic method for calculating volumes of polyhedra corresponding to Brillouin zones, Acta Cryst. Sect. A 7 (1954), 249259.
 [27]
 T. Speevak, An efficient algorithm for obtaining the volume of a special kind of pyramid and application to convex polyhedra, Math. Comp. 46 (1986), 531536. MR 829623 (87d:52012)
 [28]
 J. Stoer and C. Witzgall, Convexity and optimization in finite dimensions, SpringerVerlag, 1970. MR 0286498 (44:3707)
 [29]
 L. G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput. 8 (1979), 410421. MR 539258 (80f:68055)
 [30]
 B. Von Hohenbalken, Finding Simplicial subdivisions of polytopes, Math. Programming 21 (1981), 233234. MR 623842 (82h:52001)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
52B55
Retrieve articles in all journals
with MSC:
52B55
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718199110790242
PII:
S 00255718(1991)10790242
Article copyright:
© Copyright 1991
American Mathematical Society
