ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2019. Vol. 28

Maximizing the Sum of Radii of Balls Inscribed in a Polyhedral Set

R. Enkhbat, J. Davaadulam

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].

About the Authors

Rentsen Enkhbat, Dr. Sci. (Phys.–Math.), Prof., Institute of Mathematics, National University of Mongolia, 4, Baga toiruu, Sukhbaatar district, Ulaanbaatar, Mongolia; tel.: 976-99278403, e-mail: renkhbat46@yahoo.com

Jamsranjav Davaadulam, PhD (Mathematics), Prof., Institute of Mathematics, National University of Mongolia, 4, Baga toiruu, Sukhbaatar district, Ulaanbaatar, Mongolia; tel.: 976-99141976, e-mail: jdavaadulam@yahoo.com

For citation

Enkhbat R., Davaadulam J. Maximizing the Sum of Radii of Balls Inscribed in a Polyhedral Set. The Bulletin of Irkutsk State University. Series Mathematics, 2019, vol. 28, pp. 138-145. https://doi.org/10.26516/1997-7670.2019.28.138

Hilbert space, maximization problem, optimality conditions, optimal control, sum of radii
  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, 2010, vol. 37, pp. 1318-1327. https://doi.org/10.1016/j.cor.2009.09.017
  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, 2005, vol. 160, pp. 19-33. https://doi.org/10.1016/j.ejor.2003.06.018
  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, 2008, vol. 191, pp. 786-802. https://doi.org/10.1016/j.ejor.2007.01.054
  4. Cui Y., Xu D. Strips minimization in two-dimensional cutting stock of circular items. Computers and Operations Research, 2010, vol. 37, pp. 621-629. https://doi.org/10.1016/j.cor.2009.06.005
  5. Enkhbat R. Global optimization approach to Malfatti’s problem. Journal of Global Optimization, 2016, vol. 65, pp. 33-39. https://doi.org/10.1007/s10898-015-0372-6
  6. Enkhbat R., Barkova M. Global search method for solving Malfatti’s four-circle problem. The Bulletin of Irkutsk State University. Series Mathematics, 2016, vol. 15, pp. 38-49.
  7. Enkhbat R., Barkova M., Strekalovsky A.S. Solving Malfatti’s High Dimensional Problem by Global Optimization. Numerical Algebra, Control and Optimization, 2016, vol. 6, no. 2, pp. 153-160.
  8. Fejos Toth L. Lagerungen in der Ebene auf der Kugel und im Raum. Zweite Auflage. Grundl Math. Springer-Verlag, Wiss, 1958.
  9. Folkman J.H., Graham R.L. A packing inequality for compact subsets of the plane. Canadian Mathematical Bulletin, 1969, vol. 12, pp. 745-752.
  10. Goldberg M. On the original Malfatti problem. Mathematics Magazine, 1967, vol. 40, no. 5, pp. 241-247. https://doi.org/10.1080/0025570X.1967.11975806
  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, 2010, vol. 47, no. 1, pp. 63-81. https://doi.org/10.1007/s10898-009-9458-3
  12. Hamacher H.W., Drezner Z. Facility Location: Application and Theory. 2nd ed. Springer-Verlag, New York, 2004.
  13. Hifi M., M’Hallah R. A Literature Review on Circle and Sphere Packing Problems: Models and Methodologies. Advances in Operations Research, 2009, vol. 22. https://doi.org/10.1155/2009/150624.
  14. Huang W., Ye T. Global optimization method for finding dense packings of equal circles in a circle. European Journal of Operational Research, 2011, vol. 210, pp. 516–524. https://doi.org/10.1016/j.ejor.2010.11.020
  15. Lob H., Richmond H.W. On the solutions of the Malfatti problem for a triangle. Proc. London Math. Soc., 1930, vol. 2, no. 30, pp. 287–301. https://doi.org/10.1112/plms/s2-30.1.287
  16. Malfatti C. Memoria sopra una problema stereotomico. Memoria di Matematica e di Fisica della Societa italiana della Scienze, 1803, vol. 10, no. 1, pp. 235–244.
  17. Strekalovsky A.S. On the global extrema problem. Soviet Math. Doklad, 1987, vol. 292, no. 5, pp. 1062–1066.
  18. Zalgaller V.A. An inequality for acute triangles. Ukrainskii Geometricheskii Sbornik,1991 , vol. 35, pp. 11–14.

Full text (english)