Efficiency of the estimate refinement method for polyhedral approximation of multidimensional balls

G. K. Kamenev

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 5, pp. 756-767

Résumé

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.

Bibliographie

[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, Sovremennaya matematika. Fundamentalnye napravleniya, 22, 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, 239 pp.

[6] Lotov A. V., Bushenkov V. A., Kamenev G. K., Interactive decision maps. Approximation and visualization of Pareto frontier, Appl. Optimization, 89, Kluwer Academic Publishers, Boston–Dordrecht–New York–London, 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] 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

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

[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-vo VTs RAN, M., 2007, 230 pp. | MR

[15] Böröczky K. Jr., “Polytopal approximation bounding the number of $k$-faces”, J. of Approx. Theory, 102 (2000), 263–285 | DOI | MR | Zbl

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

[17] Dzholdybaeva S. M., Kamenev G. K., Eksperimentalnoe issledovanie approksimatsii vypuklykh tel mnogogrannikami, VTs AN SSSR, M., 1991, 51 pp.

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

[19] 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

[20] Kamenev G. K., “Asimptoticheskie svoistva metoda utochneniya otsenok pri approksimatsii mnogomernykh sharov mnogogrannikami”, Zh. vychisl. matem. i matem. fiz., 55:10 (2015), 1647–1660 | DOI | Zbl

[21] Rodzhers K., Ukladki i pokrytiya, Mir, M., 1968 | MR

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

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

[24] Grünbaum B., Convex Polytopes, Graduate Texts in Mathematics, 221, Second Edition, Springer, New York, 2003 | DOI | MR

[25] 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

[26] 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

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

[28] 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

[29] Kabatyanskii G. A., Levenshtein V. I., “O granitsakh dlya upakovok na sfere i v prostranstve”, Probl. peredachi informatsii, 14:1 (1978), 3–25 | MR