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   ; G. K. Kamenev

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 51 (2011) no. 6, pp. 1018-1031

Résumé

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.

Bibliographie

[1] Minkowskii H., “Volumen und Oberfläche”, Math. Ann., 57 (1903), 447–497 | DOI | MR

[2] Aleksandrov A. D., Vnutrennyaya geometriya vypuklykh poverkhnostei, Gostekhteorizdat, M.-L., 1948

[3] Gruber P. M., “Aspects of approximation of convex bodies”, Handbook of Convex Geometry, Ch. 1.10, v. B, Elsevier Sci., 1993, 321–345

[4] Bronshtein E. M., “Approksimatsiya vypuklykh mnozhestv mnogogrannikami”, Sovr. matem. Fundamentalnye napravleniya. Geometriya, 22, 2007, 5–37

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

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

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

[8] Sonnevend G., “An optimal sequential algorithm for the uniform approximation of convex functions on [0, 1]”, Appl. Math. and Optimizat., 10 (1983), 127–142 | DOI | MR | Zbl

[9] Moiseev N. N., Matematicheskie zadachi sistemnogo analiza, Nauka, M., 1981

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

[11] Lotov A. V., Bushenkov V. A., Kamenev G. K., Interactive decision maps: Approximation and visualization of pareto frontier, Appl. Optimizat., 89, Kluwer Acad. Publs, Boston etc., 2004 | MR | Zbl

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

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

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

[15] Kamenev G. K., “Ob effektivnosti khausdorfovykh algoritmov poliedralnoi approksimatsii vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 33:5 (1993), 796–805 | MR | Zbl

[16] Kamenev G. K., “Effektivnye algoritmy vnutrennei poliedralnoi approksimatsii negladkikh vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 39:3 (1999), 446–450 | MR | Zbl

[17] Kamenev G. K., “Ob approksimatsionnykh svoistvakh negladkikh vypuklykh diskov”, Zh. vychisl. matem. i matem. fiz., 40:10 (2000), 1464–1474 | MR | Zbl

[18] Efremov 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 | Zbl

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

[20] Kamenev G. K., Optimalnye adaptivnye metody poliedralnoi approksimatsii vypuklykh tel, VTs RAN, M., 2007

[21] Bronshtein E. M., Ivanov L. D., “O priblizhenii vypuklykh mnozhestv mnogogrannikami”, Sibirskii matem. zhurnal, 26:5 (1975), 1110–1112

[22] Dudley R., “Metric entropy of some classes of sets with differentiable boundaries”, J. Approximat. Theory, 10 (1974), 227–236 ; Corr. J. Approximat. Theory, 26 (1979), 192–193 | DOI | MR | Zbl | DOI | MR | Zbl

[23] Gruber P. M., “Asymptotic estimates for best and stepwise approximation of convex bodies. I”, Forum Math., 5 (1993), 281–297 | DOI | MR | 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] Böröczky K. Jr., “About the error term for best approximation with respect to the Hausdorff related metrics”, Discrete Comput. Geometrie, 25 (2001), 293–309 | DOI | MR

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

[28] McMullen P., Shephard G. C., Convex polytopes and the upper bound conjecture, Cambridge Univ. Press, Cambridge, 1971

[29] Efremov R. V., Kamenev G. K., “Properties of a method for polyhedral approximation of the feasible criterion set in convex multiobjective problems”, Ann. Operat. Res., 166 (2009), 271–279 | DOI | MR | Zbl

[30] Blyashke V., Krug i shar, Nauka, M., 1967

[31] Koutroufiotis D., “On Blaschke's rolling theorems”, Arch. Math., 23 (1972), 655–660 | DOI | MR | Zbl

[32] Schneider R., “Closed convex hypersurfaces with curvature restrictions”, Proc. Amer. Math. Soc., 103 (1988), 1201–1204 | DOI | MR | Zbl

[33] Leichtweiß K., “Convexity and differential geometry”, Handbook of Convex Geometry, Ch. 4.1, v. B, Elsevier Sci., 1993, 1045–1080