Maximizing the Sum of Radii of Balls
Inscribed in a Polyhedral Set
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 . Malfatti’s generalized problem was examined in [6; 7] as the convex maximization problem employing the global optimality conditions of Strekalovsky .
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: email@example.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: firstname.lastname@example.org
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
- 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
- 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
- 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
- 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
- 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
- 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.
- 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.
- Fejos Toth L. Lagerungen in der Ebene auf der Kugel und im Raum. Zweite Auflage. Grundl Math. Springer-Verlag, Wiss, 1958.
- Folkman J.H., Graham R.L. A packing inequality for compact subsets of the plane. Canadian Mathematical Bulletin, 1969, vol. 12, pp. 745-752.
- 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
- 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
- Hamacher H.W., Drezner Z. Facility Location: Application and Theory. 2nd ed. Springer-Verlag, New York, 2004.
- 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.
- 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
- 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
- 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.
- Strekalovsky A.S. On the global extrema problem. Soviet Math. Doklad, 1987, vol. 292, no. 5, pp. 1062–1066.
- Zalgaller V.A. An inequality for acute triangles. Ukrainskii Geometricheskii Sbornik,1991 , vol. 35, pp. 11–14.