Volume approximation of convex bodies by polytopes - a constructive method

ArticleOriginal scientific text

Title

Authors ¹, ², ³

Department of Mathematics, Technion I.I.T., 32000 Haifa, Israel
Equipe d'Analyse, Université Paris 6, 4, Place Jussieu, F-75252 Paris Cedex 5, France
Department of Mathematics and School of Education - Oranim, University of Haifa 31905 Haifa, Israel

Algorithms are given for constructing a polytope P with n vertices (facets), contained in (or containing) a given convex body K in

ℝ^{d}

, so that the ratio of the volumes |K∖P|/|K| (or |P∖K|/|K|) is smaller than

\frac{f (d)}{n^{\frac{2}{d - 1}}}

.

convex bodies, polytopes, approximation

U. Betke and J. M. Wills, Diophantine approximation of convex bodies, manuscript, 1979.
E. M. Bronshteĭn and L. D. Ivanov, The approximation of convex sets by polyhedra, Sibirsk. Mat. Zh. 16 (1975), 1110-1112 (in Russian); English transl.: Siberian Math. J. 16 (1975), 852-853.
R. Dudley, Metric entropy of some classes of sets with differentiable boundaries, J. Approx. Theory 10 (1974), 227-236.
L. Fejes Tóth, Lagerungen in der Ebene, auf der Kugel und im Raum, Springer, 1953, 1972.
P. M. Gruber, Approximation of convex bodies, in: Convexity and its Applications, P. M. Gruber and J. M. Wills (eds.), Birkhäuser, 1983, 131-162.
P. M. Gruber, Aspects of approximation of convex bodies, in: Handbook of Convex Geometry, vol. A, P. M. Gruber and J. M. Wills (eds.), Elsevier, 1993.
P. M. Gruber, Asymptotic estimates for best and stepwise approximation of convex bodies I, Forum Math. 5 (1993), 281-297.
P. M. Gruber, Asymptotic estimates for best and stepwise approximation of convex bodies II, ibid., 521-538.
A. M. Macbeath, An extremal property of the hypersphere, Proc. Cambridge Philos. Soc. 47 (1951), 245-247.
J. S. Müller, Approximation of the ball by random polytopes, J. Approx. Theory 63 (1990), 198-209.
E. Sas, Über eine Extremaleigenschaft der Ellipsen, Compositio Math. 6 (1939), 468-470.