Abstract
It is a well-known fact that for every polynomial-time algorithm which gives an upper bound\(\bar V(K)\) and a lower bound\(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{V} (K)\) for the volume of a convex setK⊂E d given by an oracle, the ratio\(\bar V(K)/\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{V} (K)\) is at least (cd/logd)d. Here we describe an algorithm which gives, for ε>0, in polynomial time, an upper and lower bound with the property\(\bar V(K)/\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{V} (K) \leqslant d!(1 + \varepsilon )^d\).
Article PDF
Similar content being viewed by others
References
[AK] D. Applegate, R. Kannan, Sampling and Integration of Near Log-Concave Functions, Computer Science Department Report, Carnegie-Mellon University, 1990.
[BF] I. Bárány, Z. Füredi, Computing the volume is difficult,Discrete Comput. Geom. 2 (1987), 319–326.
[BH] U. Betke, M. Henk, Estimating Sizes of a Convex Body by Successive Diameters and Widths,Mathematika 39 (1992), 247–257.
[BoF] T. Bonnesen, W. Fenchel,Theorie der konvexen Körper, Springer-Verlag, Berlin, 1934.
[DF] M. Dyer, A. Frieze. Computing the Volume of Convex Bodies: A Case Where Randomness Provably Helps, Computer Science Department Report, Carnegie-Mellon University, 1991.
[DFK] M. Dyer, A. Frieze, R. Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies,J. Assoc. Comput. Mach. 38 (1991), 1–17.
[E] G. Elekes A geometric inequality and the complexity of computing the volume.Discrete Comput. Geom. 1 (1986), 289–292.
[GLS] M. Grötschel, L. Lovász, A. Schrijver,Geometric Algorithms and Combinatorial Optimization, Springer-Verlag; Berlin, 1988.
[YN] D. B. Yudin, A. S. Nemirovskiî, Informational complexity and efficient methods for the solution of convex extremal problems,Èkonom. i Mat. Metody 12 (1976), 357–369 (Russian) (English translation,Matekon 13(3) (1977), 25–45).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Betke, U., Henk, M. Approximating the volume of convex bodies. Discrete Comput Geom 10, 15–21 (1993). https://doi.org/10.1007/BF02573960
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02573960