We consider a general sphere packing problem which is to pack nonoverlapping spheres (balls) with the maximum volume into a convex set. This problem has important applications in science and technology. We prove that this problem is equivalent to the convex maximization problem which belongs to a class of global optimization. We derive necessary and sufficient conditions for inscribing a finite number of balls into a convex compact set. In two dimensional case, the sphere packing problem is a classical circle packing problem. We show that 200 years old Malfatti’s problem [11] is a particular case of the circle packing problem. We also survey existing algorithms for solving the circle packing problems as well as their industrial applications.

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

Enkhbat R. Convex Maximization Formulation of General Sphere Packing Problem. The Bulletin of Irkutsk State University. Series Mathematics, 2020, vol. 31, pp. 142-149. https://doi.org/10.26516/1997-7670.2020.31.142

1. Dowsland K.A. Optimising the palletisation of cylinders in cases. OR Spectrum, 1991, vol. 13, pp. 204-212.

2. Drezner Z., Erkut E. Solving the continuous p-dispersionproblem using non-linear programming. Journal of the Operational Research Society, 1995, vol. 46, pp. 516-520.

3. Drezner Z. Discon: A new method for the layout problem. Operations Research, 1980, vol. 28, pp. 1375-1384.

4. Enhbat R. Global Optimization Approach to Malfatti’s Problem. Journal of Global Optimization, 2016, vol. 65, pp. 33-39.

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

6. Enkhbat R., Barkova M., Strekalovsky A. Solving Malfatti’s High Dimensional Problem by Global Optimization. Numerical Algebra, Control and Optimization, 2016, vol. 6, no. 2, pp. 153-160.

7. Erkut E. The discrete p-dispersion problem. European Journal of Operational Research, 1990, vol. 46, pp. 48-60.

8. Equation 5.19.4, NIST Digital Library of Mathematical Functions. 2013. Available at: http://dlmf.nist.gov/5.19E4.

9. Fraser H.J., George J.A. Integrated container loading software for pulp and paper industry. European Journal of Operational Research, 1994, vol. 77, pp. 466-474.

10. Hifi M., MHallah R. Approximate algorithms for constrained circular cutting problems. Computers and Operations Research, 2004, vol. 31, pp. 675-694.

11. Malfatti G. Memoria sopra una problema stereotomico. Memoria di Matematica e di Fisica della Societa italiana della Scienze, 1803, vol. 10, no. 1, pp. 235-244.

12. Martin C. How many robots can talk at the same time? Department of Mathematics, The Royal Institute of Technology, Stockholm, 2004. Available at: http://www.math.kth.se/optsyst/seminar/martinIII.html

13. Nguyen V.H., Strodiot J.J. Computing a Global Optimal Solution to a Design Centering Problem. Mathematical Programming, 1992, vol. 53, pp. 111-123.

14. Paris R.B., Kaminski D. Asymptotics and Mellin-Barnes Integrals. Cambridge University Press, 2001.

15. Strekalovsky A.S. On the global extrema problem. Soviet Math. Dokl., 1987, vol. 292, no. 5, pp. 1062-1066.

16. Strekalovsky A.S. On local search in d.c. optimization problems. Applied Mathematics and Computation, 2015, vol. 255, pp.73-83.

17. Vidigal L.M., Director S.W. A Design Centering Algorithm for Nonconvex Regions of Acceptability. IEEE Transactions on Computer-Aided-Design of Integrated Circuits and Systems, 1982, vol. CAD-1, pp. 13-24.

18. Wu Q.J., Bourland J.D. Morphology-Guided Radiosurgery Treatment Planning and Optimization for Multiple Isocenters. Medical Physics, 1992, vol. 26, pp. 2151-2160.

19. Wu A. Physics and Dosimetry of the Gamma Knife. Neurosurgery Clinics of North America, 1992, vol. 3, pp. 35-50.