Geodesic
Maximizing the sum of radii of balls inscribed in a polyhedral set
The Bulletin of Irkutsk State University. Series Mathematics, Tome 28 (2019), pp. 138-145
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The sphere packing problem is one of the most applicable areas in mathematics which finds numerous applications in science and technology [1–4; 8; 9; 11–14]. We consider a maximization problem of a sum of radii of non-overlapping balls inscribed in a polyhedral set in Hilbert space. This problem is often formulated as the sphere packing problem. We extend the problem in Hilbert space as an optimal control problem with the terminal functional and constraints for the final moment. This problem belongs to a class of nonconvex optimal control problem and application of gradient methods does not always guarantee finding a global solution to the problem. We show that the problem in a finite dimensional case for three balls (spheres) is connected to well known Malfatti’s problem [16]. Malfatti’s generalized problem was examined in [6; 7] as the convex maximization problem employing the global optimality conditions of Strekalovsky [17].
Keywords: Hilbert space, maximization problem, optimality conditions, optimal control
Mots-clés : sum of radii. 
@article{IIGUM_2019_28_a9,
     author = {R. Enkhbat and J. Davaadulam},
     title = {Maximizing the sum of radii of balls inscribed in a polyhedral set},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {138--145},
     year = {2019},
     volume = {28},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2019_28_a9/}
}
TY  - JOUR
AU  - R. Enkhbat
AU  - J. Davaadulam
TI  - Maximizing the sum of radii of balls inscribed in a polyhedral set
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2019
SP  - 138
EP  - 145
VL  - 28
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2019_28_a9/
LA  - en
ID  - IIGUM_2019_28_a9
ER  - 
%0 Journal Article
%A R. Enkhbat
%A J. Davaadulam
%T Maximizing the sum of radii of balls inscribed in a polyhedral set
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2019
%P 138-145
%V 28
%U http://geodesic.mathdoc.fr/item/IIGUM_2019_28_a9/
%G en
%F IIGUM_2019_28_a9
R. Enkhbat; J. Davaadulam. Maximizing the sum of radii of balls inscribed in a polyhedral set. The Bulletin of Irkutsk State University. Series Mathematics, Tome 28 (2019), pp. 138-145. http://geodesic.mathdoc.fr/item/IIGUM_2019_28_a9/

[1] Birgin E. G., Gentil J. M., “New and improved results for packing identical unitary radius circles within triangles, rectangles and strips”, Computer and Operations Research, 37 (2010), 1318–1327 | DOI | MR | Zbl

[2] Birgin E. G., Martinez J. M., Ronconi D. P., “Optimizing the packing of cylinders into a rectangular container: a nonlinear approach”, European Journal of Operational Research, 160 (2005), 19–33 | DOI | MR | Zbl

[3] Castillo I., Kampas F. J., Pinter J. D., “Solving circle packing problems by global optimization: numerical results and industrial applications”, European Journal of Operational Research, 191 (2008), 786–802 | DOI | MR | Zbl

[4] Cui Y., Xu D., “Strips minimization in two-dimensional cutting stock of circular items”, Computers and Operations Research, 37 (2010), 621–629 | DOI | Zbl

[5] Enkhbat R., “Global optimization approach to Malfatti's problem”, Journal of Global Optimization, 65 (2016), 33–39 | DOI | MR | Zbl

[6] Enkhbat R., Barkova M., “Global search method for solving Malfatti's four-circle problem”, The Bulletin of Irkutsk State University. Series "Mathematics", 15 (2016), 38–49 | Zbl

[7] Enkhbat R., Barkova M., Strekalovsky A. S., “Solving Malfatti's High Dimensional Problem by Global Optimization”, Numerical Algebra, Control and Optimization, 6:2 (2016), 153–160 | DOI | MR | Zbl

[8] Fejos Toth L., Lagerungen in der Ebene auf der Kugel und im Raum, Grundl Math. Wiss., Zweite Auflage, Springer-Verlag, 1958 | MR

[9] Folkman J. H., Graham R. L., “A packing inequality for compact subsets of the plane”, Canadian Mathematical Bulletin, 12 (1969), 745–752 | DOI | MR | Zbl

[10] Goldberg M., “On the original Malfatti problem”, Mathematics Magazine, 40:5 (1967), 241–247 | DOI | MR | Zbl

[11] Grosso A. R., Jamali M. J. U., Locatelli M., Schoen F., “Solving the problem of packing equal and unequal circles in a circular container”, Journal of Global Optimization, 47:1 (2010), 63–81 | DOI | MR | Zbl

[12] Hamacher H. W., Drezner Z., Facility Location: Application and Theory, 2nd ed., Springer-Verlag, New York, 2004 | MR

[13] Hifi M., M'Hallah R., “A Literature Review on Circle and Sphere Packing Problems: Models and Methodologies”, Advances in Operations Research, 22 (2009) | DOI | Zbl

[14] Huang W., Ye T., “Global optimization method for finding dense packings of equal circles in a circle”, European Journal of Operational Research, 210 (2011), 516–524 | DOI | MR

[15] Lob H., Richmond H. W., “On the solutions of the Malfatti problem for a triangle”, Proc. London Math. Soc., 2:30 (1930), 287–301 | DOI | MR

[16] Malfatti C., “Memoria sopra una problema stereotomico”, Memoria di Matematica e di Fisica della Societa italiana della Scienze, 10:1 (1803), 235–244

[17] Strekalovsky A. S., “On the global extrema problem”, Soviet Math. Doklad, 292:5 (1987), 1062–1066 | MR

[18] Zalgaller V. A., “An inequality for acute triangles”, Ukrainskii Geometricheskii Sbornik, 35 (1991), 11–14 | MR