Method for polyhedral approximation of a ball with an optimal order of growth of the facet structure cardinality

G. K. Kamenev

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 54 (2014) no. 8, pp. 1235-1248

Résumé

The problem of polyhedral approximation of a multidimensional ball is considered. It is well known that the norm of the $f$-vector (the maximum number of faces of all dimensions) of an approximating polytope grows at least as fast as $O(\delta^{(1-d)/2})$, where $\delta$ is the Hausdorff deviation and d is the space dimension. An iterative method, namely, the deep holes method is used to construct metric nets. As applied to the problem under study, the method sequentially supplements the vertex set of the polytope with its deep holes in the metric on the ball surface (i.e., with points of the surface that are farthest away from the vertices of the polytope). It is shown that the facet structure cardinality of the constructed polytope has an optimal growth rate. It is also shown that the number of faces of all dimensions in the approximating polytopes generated by the method is asymptotically proportional to the number of their vertices. Closed-form expressions for the constants are obtained, which depend only on the dimension of the space, including the case of high dimensions. For low dimensions ($d$ ranging from $3$ to $5$), upper bounds for the growth rate of the number of faces of all dimensions are obtained depending on the accuracy of the approximation.

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

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

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

[4] Lotov A. V., Bushenkov V. A., Kamenev G. K., Interactive decision maps. Approximation and visualization of pareto frontier, Appl. Optimization, 89, Kluwer, London, 2004, 310 pp. | DOI

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

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

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

[8] Kamenev G. K., “Approksimatsiya vpolne ogranichennykh mnozhestv metodom Glubokikh Yam”, Zh. vychisl. matem. i matem. fiz., 41:11 (2001), 1751–1760

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

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

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

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

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

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

[15] Brënsted A., Vvedenie v teoriyu vypuklykh mnogogrannikov, Mir, M., 1988

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

[17] Kolmogorov A. N., Tikhomirov V. M., “$\mathcal{E}$-entropiya i $\mathcal{E}$-emkost mnozhestv v funktsionalnykh prostranstvakh”, Uspekhi matem. nauk, 14:2 (1959), 3–86

[18] Rodzhers Ch. A., Ukladki i pokrytiya, Mir, M., 1968

[19] Böröczky K. (Jr.), Finite Packing and covering, Cambridge University Press, 2004

[20] Schneider R., “Zur optimalen approximation konvexer hyperflachen durch polyeder”, Math. Ann., 256:3 (1981), 289–301 | DOI

[21] Yaglom I. M., “Nekotorye rezultaty, kasayuschiesya raspolozhenii v $n$-mernom prostranstve”: Tot L. F., Raspolozheniya na ploskosti, na sfere i v prostranstve, Fizmatlit, M., 1958

[22] Grünbaum B., Convex Polytopes, Graduate Texts in Mathematics, 221, Second Edition, Springer, Berlin, 2003 | DOI

[23] McMullen P., Shephard G. C., Convex Polytopes and the upper bound conjecture, Cambridge Cambridge University Press, 1971

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

[25] Graham R. L., Lubachevsky B. D., Nurmela K. J., Östergård P. R. J., “Dense packings of congruent circles in a circle”, Discrete Math., 181:1–3 (1998), 139–154 | DOI

[26] Pfoertner H., Densest packings of $n$ equal spheres in a sphere of radius 1. Largest Possible Radii, , 2008 http://www.randomwalk.de/sphere/insphr/spisbest.txt

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

[28] McMullen P., “The maximum numbers of faces of convex polytope”, Math., 17 (1970), 179–184

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

[30] Ziegler G. M., Lectures on Polytopes, Graduate texts in mathematics, 152, Revised First Edition, Springer, Berlin, 1995 | DOI