Geodesic
Asymptotic properties of the estimate refinement method in polyhedral approximation of multidimensional balls
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 10, pp. 1647-1660 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{ZVMMF_2015_55_10_a3,
     author = {G. K. Kamenev},
     title = {Asymptotic properties of the estimate refinement method in polyhedral approximation of multidimensional balls},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1647--1660},
     year = {2015},
     volume = {55},
     number = {10},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_10_a3/}
}
TY  - JOUR
AU  - G. K. Kamenev
TI  - Asymptotic properties of the estimate refinement method in polyhedral approximation of multidimensional balls
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2015
SP  - 1647
EP  - 1660
VL  - 55
IS  - 10
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_10_a3/
LA  - ru
ID  - ZVMMF_2015_55_10_a3
ER  - 
%0 Journal Article
%A G. K. Kamenev
%T Asymptotic properties of the estimate refinement method in polyhedral approximation of multidimensional balls
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2015
%P 1647-1660
%V 55
%N 10
%U http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_10_a3/
%G ru
%F ZVMMF_2015_55_10_a3
G. K. Kamenev. Asymptotic properties of the estimate refinement method in polyhedral approximation of multidimensional balls. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 10, pp. 1647-1660. http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_10_a3/

[1] Gruber P. M., “Aspects of approximation of convex bodies”, Handbook of Convex Geometry, Ch. 1.10, eds. P. M. Gruber, J. M. Wills, Elsevier Sci. Publishers B. V., 1993, 321–345 | MR

[2] Bronshtein E. M., “Approksimatsiya vypuklykh mnozhestv mnogogrannikami”, Geometriya, SMFN, 22, RUDN, M., 2007, 5–37 | Zbl

[3] Pontryagin L. S., Boltyanskii V. G., Gamkrelidze R. V., Mischenko E. F., Matematicheskaya teoriya optimalnykh protsessov, Nauka, M., 1969

[4] Lotov A. V., “O ponyatii obobschennykh mnozhestv dostizhimosti i ikh postroenii dlya lineinykh upravlyaemykh sistem”, Dokl. AN SSSR, 250:5 (1980), 1081–1083 | MR | Zbl

[5] Lotov A. V., Bushenkov V. A., Kamenev G. K., Chernykh O. L., Kompyuter i poisk kompromissa. Metod dostizhimykh tselei, Nauka, M., 1997

[6] Lotov A. V., Bushenkov V. A., Kamenev G. K., Interactive decision maps. Approximation and visualization of Pareto frontier, Appl. Optimization, 89, Kluwer, New York, 2004, 310 pp. | DOI | MR | Zbl

[7] Bushenkov V. A., Lotov A. V., Metody postroeniya i ispolzovaniya obobschennykh mnozhestv dostizhimosti, VTs AN SSSR, M., 1982

[8] Kamenev G. K., Issledovanie iteratsionnykh metodov approksimatsii vypuklykh mnozhestv mnogogrannikami, VTs AN SSSR, M., 1986

[9] Kamenev G. K., “Issledovanie odnogo algoritma approksimatsii vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 34:4 (1994), 608–616 | MR | Zbl

[10] Kamenev G. K., “Effektivnye algoritmy approksimatsii negladkikh vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 39:3 (1999), 423–427 | MR | Zbl

[11] Efpemov R. V., Kamenev G. K., “Apriornaya otsenka asimptoticheskoi effektivnosti odnogo klassa algoritmov poliedralnoi approksimatsii vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 42:1 (2002), 23–32 | MR

[12] Kamenev G. K., “Skorost skhodimosti adaptivnykh metodov poliedralnoi approksimatsii vypuklykh tel na nachalnom etape”, Zh. vychisl. matem. i matem. fiz., 48:5 (2008), 35–50

[13] Efremov R. V., Kamenev G. K., “Ob optimalnom poryadke rosta chisla vershin i gipergranei v klasse khausdorfovykh metodov poliedralnoi approksimatsii vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 51:6 (2011), 1018–1031 | MR | Zbl

[14] Kamenev G. K., Optimalnye adaptivnye metody poliedralnoi approksimatsii vypuklykh tel, Izd. VTs RAN, M., 2007, 230 pp.

[15] Dzholdybaeva S. M., Kamenev G. K., “Chislennoe issledovanie effektivnosti algoritma approksimatsii vypuklykh tel mnogogrannikami”, Zh. vychisl. matem. i matem. fiz., 32:6 (1992), 857–866 | MR | Zbl

[16] Kamenev G. K., Chislennoe issledovanie effektivnosti metodov poliedralnoi approksimatsii vypuklykh tel, Izd. VTs RAN, M., 2010, 118 pp.

[17] Böröczky K. (Jr.), “Polytopal Approximation Bounding the Number of $k$-Faces”, J. of Approx. Theory, 102 (2000), 263–285 | DOI | MR | Zbl

[18] Böröczky K. (Jr.), Fodor F., Vígh V., “Approximating 3-dimensional convex bodies by polytopes with a restricted number of edges”, Beit. Alg. Geom., 49 (2008), 177–193 | MR | Zbl

[19] Kamenev G. K., “Approksimatsiya vpolne ogranichennykh mnozhestv metodom glubokikh yam”, Zh. vychisl. matem. i matem. fiz., 41:11 (2001), 1751–1760 | MR | Zbl

[20] Kamenev G. K., Lotov A. V., Maiskaya T. S., “Postroenie suboptimalnykh pokrytii mnogomernoi edinichnoi sfery”, Dokl. AN, 444:2 (2012), 153–155 | Zbl

[21] Kamenev G. K., Lotov A. V., Maiskaya T. S., “Iterativnyi metod postroeniya pokrytii mnogomernoi edinichnoi sfery”, Zh. vychisl. matem. i matem. fiz., 53:2 (2013), 181–194 | DOI | MR | Zbl

[22] Kamenev G. K., “Poliedralnaya approksimatsiya shara Metodom Glubokikh Yam s optimalnym poryadkom rosta moschnosti grannoi struktury”, Chislennaya geometriya, postroenie raschetnykh setok i vysokoproizvoditelnye vychisleniya, NUMGRID2010, Trudy Mezhdunar. konf. (Moskva, 11–13 oktyabrya 2010 g.), Izd. Folium, M., 2010, 47–52 | MR

[23] Kamenev G. K., “Metod poliedralnoi approksimatsii shara s optimalnym poryadkom rosta moschnosti grannoi struktury”, Zh. vychisl. matem. i matem. fiz., 54:8 (2014), 1235–1248 | DOI | Zbl

[24] Rodzhers K., Ukladki i pokrytiya, Mir, M., 1968

[25] Konvei Dzh., Sloen N., Upakovki sharov, reshetki i gruppy, v. 1, Mir, M., 1990

[26] Grünbaum B., Convex polytopes, Graduate texts in mathematics, 221, Second Edition, Springer, Berlin, 2003 | DOI | MR

[27] Kamenev G. K., “Ob odnom klasse adaptivnykh skhem approksimatsii vypuklykh tel mnogogrannikami”, Matem. modelirovanie i diskretnaya optimizatsiya, VTs AN SSSR, M., 1988, 3–9

[28] Kamenev G. K., “Ob odnom klasse adaptivnykh algoritmov approksimatsii vypuklykh tel mnogogrannikami”, Zh. vychisl. matem. i matem. fiz., 32:1 (1992), 136–152 | MR

[29] Leikhtveis K., Vypuklye mnozhestva, Nauka, M., 1985

[30] McMullen P., “The maximum numbers of faces of convex polytope”, Mathematica, 17 (1970), 179–184 | MR | Zbl

[31] Brensted A., Vvedenie v teoriyu vypuklykh mnogogrannikov, Mir, M., 1988

[32] Seidel R., “The upper bound theorem for polytopes: an easy proof of its asymptotic version”, Comput. Geometry: Theory and Applications, 5 (1995), 115–116 | DOI | MR | Zbl