Geodesic
Convex maximization formulation of general sphere packing problem
The Bulletin of Irkutsk State University. Series Mathematics, Tome 31 (2020), pp. 142-149 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider a general sphere packing problem which is to pack non-overlapping 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.
Keywords: sphere packing problem, convex maximization, optimality conditions
Mots-clés : Malfatti's problem. 
@article{IIGUM_2020_31_a9,
     author = {R. Enkhbat},
     title = {Convex maximization formulation of general sphere packing problem},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {142--149},
     year = {2020},
     volume = {31},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2020_31_a9/}
}
TY  - JOUR
AU  - R. Enkhbat
TI  - Convex maximization formulation of general sphere packing problem
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2020
SP  - 142
EP  - 149
VL  - 31
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2020_31_a9/
LA  - en
ID  - IIGUM_2020_31_a9
ER  - 
%0 Journal Article
%A R. Enkhbat
%T Convex maximization formulation of general sphere packing problem
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2020
%P 142-149
%V 31
%U http://geodesic.mathdoc.fr/item/IIGUM_2020_31_a9/
%G en
%F IIGUM_2020_31_a9
R. Enkhbat. Convex maximization formulation of general sphere packing problem. The Bulletin of Irkutsk State University. Series Mathematics, Tome 31 (2020), pp. 142-149. http://geodesic.mathdoc.fr/item/IIGUM_2020_31_a9/

[1] Dowsland K. A., “Optimising the palletisation of cylinders in cases”, OR Spectrum, 13 (1991), 204–212 | DOI | Zbl

[2] Drezner Z., Erkut E., “Solving the continuous p-dispersionproblem using non-linear programming”, Journal of the Operational Research Society, 46 (1995), 516–520 | DOI | Zbl

[3] Drezner Z., “Discon: A new method for the layout problem”, Operations Research, 28 (1980), 1375–1384 | DOI | Zbl

[4] Enhbat R., “Global Optimization Approach to Malfatti's Problem”, Journal of Global Optimization, 65 (2016), 33–39 | DOI | MR

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

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

[7] Erkut E., “The discrete p-dispersion problem”, European Journal of Operational Research, 46 (1990), 48–60 | DOI | MR | Zbl

[8] Equation 5.19.4, NIST Digital Library of Mathematical Functions, , 2013 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, 77 (1994), 466–474 | DOI | Zbl

[10] Hifi M., MHallah R., “Approximate algorithms for constrained circular cutting problems”, Computers and Operations Research, 31 (2004), 675–694 | DOI | Zbl

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

[12] Martin C., How many robots can talk at the same time?, Department of Mathematics, The Royal Institute of Technology, Stockholm, 2004 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, 53 (1992), 111–123 | DOI | MR | Zbl

[14] Paris R. B., Kaminski D., Asymptotics and Mellin-Barnes Integrals, Cambridge University Press, 2001 | MR | Zbl

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

[16] Strekalovsky A. S., “On local search in d.c. optimization problems”, Applied Mathematics and Computation, 255 (2015), 73–83 | DOI | MR | Zbl

[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, CAD-1 (1982), 13–24 | DOI

[18] Wu Q. J., Bourland J. D., “Morphology-Guided Radiosurgery Treatment Planning and Optimization for Multiple Isocenters”, Medical Physics, 26 (1992), 2151–2160

[19] Wu A., “Physics and Dosimetry of the Gamma Knife”, Neurosurgery Clinics of North America, 3 (1992), 35–50 | DOI