Efficiency of the estimate refinement method for polyhedral approximation of multidimensional balls
- Authors: Kamenev G.K.1
-
Affiliations:
- Dorodnicyn Computing Center, Federal Research Center “Computer Science and Control”
- Issue: Vol 56, No 5 (2016)
- Pages: 744-755
- Section: Article
- URL: https://journal-vniispk.ru/0965-5425/article/view/178430
- DOI: https://doi.org/10.1134/S0965542516050080
- ID: 178430
Cite item
Abstract
The estimate refinement method for the polyhedral approximation of convex compact bodies is analyzed. When applied to 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. In previous studies, for the approximation of a multidimensional ball, the convergence rates of the method were estimated in terms of the number of faces of all dimensions and the cardinality of the facial structure (the norm of the f-vector) of the constructed polytope was shown to have an optimal rate of growth. In this paper, the asymptotic convergence rate of the method with respect to faces of all dimensions is compared with the convergence rate of best approximation polytopes. Explicit expressions are obtained for the asymptotic efficiency, including the case of low dimensions. Theoretical estimates are compared with numerical results.
About the authors
G. K. Kamenev
Dorodnicyn Computing Center, Federal Research Center “Computer Science and Control”
Author for correspondence.
Email: gkk@ccas.ru
Russian Federation, ul. Vavilova 40, Moscow, 119333
Supplementary files
