On the complexity and methods of polyhedral approximations of convex bodies with a partially smooth boundary

N. B. Brusnikina   ; G. K. Kamenev

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 45 (2005) no. 9, pp. 1555-1565

Résumé

Polyhedral approximation of nonsmooth convex compact bodies with a boundary having smooth portions of positive Gaussian curvature is considered. Examples of such bodies are reachable sets of dynamic control systems. The complexity of solving such approximation problems is estimated, and optimal approximation methods are discussed.

Bibliographie

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

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

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

[4] Chernousko F. L., Otsenivanie fazovogo sostoyaniya dinamicheskikh sistem, Nauka, M., 1988 | MR

[5] Lotov A. B., “Chislennyi metod postroeniya mnozhestv dostizhimosti dlya lineinoi upravlyaemoi sistemy”, Zh. vychisl. matem. i matem. fiz., 12:3 (1972), 785–787 | MR

[6] Lotov A. B., “Chislennyi metod issledovaniya nepreryvnosti vremeni bystrodeistviya v lineinykh sistemakh i resheniya zadachi Koshi dlya uravneniya Bellmana”, Zh. vychisl. matem. i matem. fiz., 13:5 (1973), 1315–1318 | MR

[7] Lotov A. B., “Chislennyi metod postroeniya mnozhestv dostizhimosti dlya lineinykh upravlyaemykh sistem s fazovymi ogranicheniyami”, Zh. vychisl. matem. i matem. fiz., 15:1 (1975), 67–68 | MR

[8] Vasilev N. S., “K otyskaniyu globalnogo minimuma kvazivognutoi funktsii”, Zh. vychisl. matem. i matem. fiz., 23:2 (1983), 307–313 | MR

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

[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. Optimization, 89, Kluwer Academic Publishers, Boston, 2004 | MR | Zbl

[12] Gruber P. M., “Approximation of convex bodies”, Convexity and its Applics, Birkhaüser, Basel etc., 1983, 131–162 | MR

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

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

[15] Schneider R., Wieacker J. A., “Approximation of convex bodies by polytopes”, Bull. London Math. Soc., 13 (1981), 149–156 | DOI | MR | Zbl

[16] Gruber P. M., Kenderov P., “Approximation of convex bodies by polytopes”, Rendiconti Circolo mat. Palermo. Ser. II, 31:2 (1982), 195–225 | DOI | MR | Zbl

[17] Böröczky K. Jr., “Approximation of General Smooth Convex Bodies”, Advanc. Math., 153 (2000), 325–341 | DOI | MR

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

[19] Blyashke V., Krug i shar, Nauka, M., 1967 | MR

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

[21] Brooks I. N., Strantzen J. B., “Blaschke's rolling theorem in $R^n$”, Mem. Amer. Math. Soc., 80, no. 405, Providence, 1989, 2–5 | MR

[22] Leichtweiss K., “Convexity and differential geometry”, Handbook of Convex Geometry, Ch. 4.1, v. V, eds. P. M. Gruber, J. M. Wills, Elsevier Science Publishers, 1993, 1045–1080 | MR

[23] Leikhtveis K., Vypuklye mnozhestva, Nauka, M., 1985 | MR

[24] Rokafellar R., Vypuklyi analiz, Mir, M., 1973

[25] Schneider R., “Zur optimalen Approximation konvexer Hyperflachen durch Polyeder”, Math. Ann., 256:3 (1981), 289–301 | DOI | MR | Zbl

[26] Schneider R., “Polyhedral approximation of smooth convex bodies”, J. Math. Analys. and Appl., 128:2 (1987), 470–474 | DOI | MR | Zbl

[27] Gruber P. M., “Volume approximation of convex bodies by inscribed polytopes”, Math. Ann., 281:2 (1988), 229–245 | DOI | MR | Zbl

[28] Gruber P. M., “Volume approximation of convex bodies by circumscribed polytopes”, Applied Geometry and Discrete Mathematics. The Victor Klee Festschrift, DIMACS Ser., 4, Amer. Math. Soc., Providence, RI, 1991, 309–317 | MR

[29] Gruber P. M., “Asymptotic estimates for best and stepwise approximation of convex bodies, I”, Forum Math., 5 (1993), 281–297 | DOI | MR | Zbl

[30] Gruber P. M., “Asymptotic estimates for best and stepwise approximation of convex bodies, II”, Forum Math., 5 (1993), 521–538 | DOI | MR

[31] Gurevich V., Volmen G., Teoriya razmernosti, Izd-vo inostr. lit., M., 1948

[32] Gruber P. M., “Aspects of Approximation of Convex Bodies”, Handbook of Convex Geometry, Ch. 1.10, 321–345

[33] Gruber P. M., “Approximation by convex polytopes”, Polytopes: Abstract, Convex and Computational, Kluwer Acad. Publ., 1994, 173–203 | MR | Zbl

[34] Gruber P. M., “Comparisons of best and random approximation of convex bodies by polytopes”, Rendiconti Circolo mat. Palermo. Ser. II, 50, Suppl. (1997), 189–216 | MR | Zbl

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

[36] Lotov A. V., Bushenkov V. A., Kamenev G. K., Metod dostizhimykh tselei. Matematicheskie osnovy i ekologicheskie prilozheniya, Mellen Press, New York, USA, Lewiston, 1999

[37] Samsonov S. L., “Vosstanovlenie vypuklogo mnozhestva po ego opornoi funktsii s zadannoi tochnostyu”, Vestn. MGU. Ser. 15. Vychisl. matem. i kibernetika, 1983, no. 1, 68–71 | MR | Zbl

[38] Vasilev N. S., “O neuluchshaemykh otsenkakh approksimatsii silno vypuklykh tel”, Vopr. kibernetiki, 136 (1988), 49–56 | MR

[39] Polovinkin E. S., Balashov M. V., Elementy vypuklogo i silno vypuklogo analiza, Fizmatlit, M., 2004

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

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

[42] Kamenev G. K., “Sopryazhennye adaptivnye algoritmy poliedralnoi approksimatsii vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 42:9 (2002), 1351–1367 | MR | Zbl

[43] Kamenev G. K., “Metod poliedralnoi approksimatsii vypuklykh tel, optimalnyi po poryadku chisla raschetov opornoi i distantsionnoi funktsii”, Dokl. RAN, 388:3 (2003), 309–311 | MR

[44] Kamenev G. K., “Samodvoistvennye adaptivnye algoritmy poliedralnoi approksimatsii vypuklykh tel”, Zh. vychisl. matem. i matem. fiz., 43:8 (2003), 1123–1137 | MR | Zbl