zbMATH — the first resource for mathematics

Computing the volume is difficult. (English) Zbl 0628.68041
Assuming the black box model of a convex set in d-dimensional Euclidean space, algorithms for computing the volume or the width of convex sets are analyzed. Negative results are proved: For every polynomial time algorithm which gives an upper bound \(\overline{vol}\) and a lower bound \(\underline{vol}\) for the volume of a convex set in d-dimensional Euclidean space, there exists a convex set such that the ratio \(\overline{vol}/\underline{vol}\) is greater than \((cd/\log d)^ d\). Similarly, for polynomial time algorithms calculating the width of a convex set (bounds \(\bar w\) and \(\underline w\)), there exists a convex set such that \(\bar w/\underline w>(d/(c \log d))^{1/2}\).
Reviewer: R.Klette

68Q25 Analysis of algorithms and problem complexity
52A37 Other problems of combinatorial convexity
52A40 Inequalities and extremum problems involving convexity in convex geometry
Full Text: DOI
[1] I. Bárány and Z. Füredi, Approximation of the ball by polytopes having few vertices, to appear.
[2] Bourgain, J.; Milman, V. D., Sections euclidiennes et volume des corps symetriques convexes dans \(R n,\) C. R. Acad. Sci. Paris Sér. I, 300, 435-437, (1985) · Zbl 0576.52002
[3] Buchta, C.; Müller, J.; Tichy, R. F., Stochastical approximation of convex bodies, Math. Ann., 271, 225-235, (1985) · Zbl 0543.52003
[4] L. Danzer, B. Grünbaum, and V. Klee, Helly’s theorem and its relatives, inProceedings of Symposia in Pure Math, Vol. VII (V. Klee, ed.), Providence, RI, 1983.
[5] G. Elekes, A geometric inequality and the complexity of measuring the volume,Discrete Comput. Geom., to appear. · Zbl 0611.52010
[6] L. Fejes Tóth,Regular Figures, Pergamon Press, Oxford, 1964. · Zbl 0134.15705
[7] M. Grötschel, L. Lovász, and A. Schrijver,Combinatorial Optimization and the Ellipsoid Method, Springer-Verlag, New York, 1987.
[8] L. Lovász, private communication, 1983.
[9] L. Lovász, An algorithmic theory of numbers, graphs and convexity, Preprint, Report No. 85368-OR, University of Bonn, 1985.
[10] Macbeath, A. M., An extremal property of the hypersphere, Math. Proc. Cambridge Phil. Soc., 47, 245-247, (1951) · Zbl 0042.40801
[11] W. O. J. Moser and J. Pach,Research Problems in Discrete Geometry, Problem 76, Montreal, 1985.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.