R. V. Efremov, G. K. Kamenev, “Optimal growth order of the number of vertices and facets in the class of Hausdorff methods for polyhedral approximation of convex bodies”, Zh. Vychisl. Mat. Mat. Fiz., 2011, Volume 51, Number 6,Pages <nobr>1018

This article is cited in 8 papers

Optimal growth order of the number of vertices and facets in the class of Hausdorff methods for polyhedral approximation of convex bodies

R. V. Efremov^a, G. K. Kamenev^b

^a 28933 Mostoles, Madrid (España), Universidad Rey Juan Carlos
^b Dorodnicyn Computing Center, Russian Academy of Sciences, ul. Vavilova 40, Moscow, 119333 Russia

Abstract: The internal polyhedral approximation of convex compact bodies with twice continuously differentiable boundaries and positive principal curvatures is considered. The growth of the number of facets in the class of Hausdorff adaptive methods of internal polyhedral approximation that are asymptotically optimal in the growth order of the number of vertices in approximating polytopes is studied. It is shown that the growth order of the number of facets is optimal together with the order growth of the number of vertices. Explicit expressions for the constants in the corresponding bounds are obtained.

Key words: smooth convex body, polyhedral approximation, approximation method, optimal methods, convergence rate of approximation, facet structure.

UDC: 519.626

Received: 25.08.2010
Revised: 20.10.2010