|
This article is cited in 2 scientific papers (total in 2 papers)
Asymptotic properties of the estimate refinement method in polyhedral approximation of multidimensional balls
G. K. Kamenev Dorodnicyn Computing Center, Russian Academy of Sciences, ul. Vavilova 40, Moscow, 119333, Russia
Abstract:
The estimate refinement method for the polyhedral approximation of convex compact bodies is considered. In the approximation of convex bodies with a smooth boundary, this method is known to generate polytopes with an optimal order of growth of the number of vertices and facets depending on the approximation error. The properties of the method are examined as applied to the polyhedral approximation of a multidimensional ball. As vertices of approximating polytopes, the method is shown to generate a deep holes sequence on the surface of the ball. As a result, previously obtained combinatorial properties of convex hulls of the indicated sequences, namely, the convergence rates with respect to the number of faces of all dimensions and the optimal growth of the cardinality of the facial structure (of the norm of the $f$-vector) can be extended to such polytopes. The combinatorial properties of the approximating polytopes generated by the estimate refinement method are compared to the properties of polytopes with a facial structure of extremal cardinality. It is shown that the polytopes generated by the method are similar to stacked polytopes, on which the minimum number of faces of all dimensions is attained for a given number of vertices.
Key words:
convex bodies, multidimensional ball, polyhedral approximation, estimate refinement method, vertices, facets, faces, facial structure, $f$-vector, convergence rate.
Received: 18.12.2014 Revised: 27.01.2015
Citation:
G. K. Kamenev, “Asymptotic properties of the estimate refinement method in polyhedral approximation of multidimensional balls”, Zh. Vychisl. Mat. Mat. Fiz., 55:10 (2015), 1647–1660; Comput. Math. Math. Phys., 55:10 (2015), 1619–1632
Linking options:
https://www.mathnet.ru/eng/zvmmf10279 https://www.mathnet.ru/eng/zvmmf/v55/i10/p1647
|
|