Volume 27, No 4, 2020, P. 58-79

UDC 514.174.2
P. D. Lebedev, V. N. Ushakov, and A. A. Uspenskii
Numerical methods for constructing suboptimal packings of nonconvex domains with curved boundary

Abstract:
We study the problem of constructing some optimal packings of simply-connected nonconvex plane domains with a union of congruent circles. We consider the minimization of the radius of circles if the number of the circles is fixed. Using subdifferential calculus, we develop theoretical methods for solution of the problem and propose an approach for constructing some suboptimal packings close to optimal. In the numerical algorithms, we use the iterative procedures and take into account mainly the location of the current center of a packing element, the centers of the nearest neighboring elements, and the points of the boundary of the domain. The algorithms use the same supergradient ascent scheme whose parameters can be adapted to the number of packing elements and the geometry of the domain. We present a new software package whose efficiency is demonstrated by several examples of numerical construction of some suboptimal packings of the nonconvex domains bounded by the Cassini oval, a hypotrochoid, and a cardioid.
Illustr. 6, bibliogr. 37.

Keywords: packing, maximization, optimization, algorithm, numerical procedure, directional derivative, superdifferential, approximation, supergradient ascent.

DOI: 10.33048/daio.2020.27.678

Pavel D. Lebedev ¹
Vladimir N. Ushakov ¹
Aleksandr A. Uspenskii ¹
1. Krasovskii Institute of Mathematics and Mechanics,
16 Sofya Kovalevskaya Street, 620990 Yekaterinburg, Russia
e-mail: pleb@yandex.ru, ushak@imm.uran.ru, uspen@imm.uran.ru

Received December 27, 2019
Revised July 27, 2020
Accepted July 29, 2020

References

[1] N. N. Krasovskii and A. I. Subbotin, Positional Differential Games (Nauka, Moscow, 1974) [Russian].

[2] V. N. Ushakov, A. A. Uspenskii, and A. G. Malev, An estimate of the stability defect for a positional absorption set subjected to discriminant transformations, Tr. Inst. Mat. Mekh. 17 (2), 209–224 (2011) [Russian] [Proc. Steklov Inst. Math. 279 (Suppl. 1), 113–129 (2012)].

[3] V. N. Ushakov, P. D. Lebedev, and N. G. Lavrov, Algorithms for optimal packings in ellipse, Vestn. Yuzhno-Ural. Gos. Univ., Ser. Mat. Model. Program. 10 (3), 67–79 (2017) [Russian].

[4] P. D. Lebedev and A. L. Kazakov, Iterative methods for the construction of planar packings of circles of different size, Tr. Inst. Mat. Mekh. 24 (2), 141–151 (2018) [Russian].

[5] J. Machchhar and G. Elber, Dense packing of congruent circles in free-form non-convex containers, Comput. Aided Geom. Des. 52–53, 13–27 (2017).

[6] L. Meng, C. Wang, and X. Yao, Non-convex shape effects on the dense random packing properties of assembled rods, Physica A, 490, 212–221 (2017).

[7] M. Locatelli and U. Raber, Packing equal circles in a square: A deterministic global optimization approach, Discrete Appl. Math. 122, 139–166 (2017).

[8] Y. Li and H. Akeb, Basic heuristics for packing a large number of equal circles (Univ. Picardie Jules Verne, Amiens, 2005). Available at
www.researchgate.net/publication/250761942_Basic_Heuristics_for_Packing_a_Great_Number_of_Equal_Circles (accessed Aug. 13, 2020).

[9] I. Litvinchev and L. Ozuna, Approximate packing circles in a rectangular container: Valid inequalities and nesting, J. Appl. Res. Technol. 12 (4), 716–723 (2014).

[10] Yu. G. Stoyan and G. Yas’kov, A mathematical model and a solution method for the problem of placing various-sized circles into a strip, Eur. J. Oper. Res. 156, 590–600 (2004).

[11] Yu. G. Stoyan and G. Yas’kov, Packing identical spheres into a rectangular parallelepiped, in Intelligent Decision Support: Current Challenges and Approaches (Gabler-Verl., Wiesbaden, 2008), pp. 46–67.

[12] M. Hifi and R. M’Hallah, Approximate algorithms for constrained circular cutting problems, Comput. Oper. Res. 31, 675–694 (2004).

[13] A. M. Chugai, A solution to the disk packing problem in a convex polygon with the use of a modified method of tapering neighborhoods, Radioélektron. Inform., No. 1, 58–63 (2005) [Russian].

[14] P. D. Lebedev and A. A. Uspenskii, Construction of the optimal result function and dispersing lines in time-optimal problems with a nonconvex target set, Tr. Inst. Mat. Mekh. 22 (2), 188–198 (2016) [Russian].

[15] A. L. Kazakov, A. A. Lempert, and T. T. Ta, The sphere packing problem into bounded containers in three-dimension non-Euclidean space, IFACPapersOnLine 51 (32), 782–787 (2018).

[16] A. L. Kazakov, A. A. Lempert, and H. L. Nguyen, An algorithm of packing congruent circles in a multiply connected set with non-Euclidean metrics, Vychisl. Metody Program. 17 (2), 177–188 (2016) [Russian].

[17] A. L. Kazakov, A. A. Lempert, and H. L. Nguyen, The problem of the optimal packing of the equal circles for special non-Euclidean metric, Commun. Comput. Inf. Sci. 661, 58–68 (2017).

[18] P. D. Lebedev and A. A. Uspenskii, Algorithms of optimal packing construction in a 3-dimensional Euclidian space, in Modern Problems in Math?ematics and Its Applications (Proc. 47th Int. Youth School-Conf. MPMA 2016, Yekaterinburg, Russia, Jan. 31–Feb. 6, 2016) (RWTH Aachen Univ., Aachen, 2016), pp. 84–93 (CEUR Workshop Proc.; Vol. 1662). Available at www.ceur-ws.org/Vol-1662 (accessed Aug. 13, 2020).

[19] A. I. Subbotin, Generalized Solutions of First-Order PDEs: The Dynamical Optimization Perspective (Birkhäuser, Boston, 1995; Inst. Comput. Technol., Moscow, 2003 [Russian]).

[20] V. F. Demyanov and L. V. Vasilyev, Non-Differentiable Optimization (Nauka, Moscow, 1981) [Russian].

[21] I. V. Bychkov, A. L. Kazakov, A. A. Lempert, D. S. Bukharov, and A. B. Stolbov, An intelligent management system for the development of a regional transport logistics infrastructure, Probl. Upr., No. 1, 27–35 (2014) [Russian] [Autom. Remote Control. 77 (2), 332–343 (2016)].

[22] V. L. Rvachov and Yu. G. Stoyan, The problem of optimal placement of circular ingots, Kibernetika, No. 3, 77–83 (1965) [Russian].

[23] I. Castillo, F. J. Kampas, and J. D. Pinter, Solving circle packing problems by global optimization: Numerical results and industrial applications, Eur. J. Oper. Res. 191 (3), 786–802 (2008).

[24] F. Harary, W. Randolph, and P. G. Mezey, A study of maximum unitcircle caterpillars – tools for the study of the shape of adsorption patterns, Discrete Appl. Math. 67 (1–3), 127–135 (1996).

[25] A. V. Eremeev, L. A. Zaozerskaya, and A. A. Kolokolov, The set covering problem: Complexity, algorithms, and experimental investigations, Diskretn. Anal. Issled. Oper., Ser. 2, 7 (2), 22–46 (2000) [Russian].

[26] R. Rockafellar, Convex Analysis (Princeton Univ., Princeton, 1970; Mir, Moscow, 1973 [Russian]).

[27] P. D. Lebedev and A. V. Ushakov, Approximating sets on a plane with optimal sets of circles, Avtom. Telemekh., No. 3, 79–90 (2012) [Russian] [Autom. Remote Control. 73 (3), 485–493 (2012)].

[28.] A. G. Sukharev, A. V. Timokhov, and V. V. Fyodorov, A Course in Optimization Methods (Nauka, Moscow, 1986) [Russian].

[29] E. A. Nurminskii and D. Tien, Method of conjugate subgradients with constrained memory, Avtom. Telemekh., No. 4, 67–80 (2014) [Russian] [Autom. Remote Control. 75 (4), 646–656 (2012)].

[30] E. A. Vorontsova, Linear tolerance problem for input-output model with interval data, Vychisl. Tekhnol. 22 (2), 67–84 (2017) [Russian].

[31] A. V. Gasnikov, P. E. Dvurechenskii, D. I. Kamzolov, Yu. E. Nesterov, V. G. Spokoiny, P. I. Stetsyuk, A. L. Suvorikova, and A. V. Chernov, Searching for equilibriums in multistage transport models, Tr. Mosk. Fiz.-Tekh. Inst. 7 (4), 143–155 (2015) [Russian].

[32] P. D. Lebedev, A program for calculating the optimal coverage of a hemisphere with a set of spherical segments, Certificate of State Registration No. 2015661543 from 29.10.2015 [Russian].

[33] L. F. Tóth, Lagerungen in der Ebene, auf der Kugel und im Raum (Springer, Heidelberg, 1953) (Grundlehren Math. Wiss., Vol. 65) [German]; (Fizmatgiz, Moscow, 1958) [Russian].

[34] L. M. Mestetskii, Continuous Morphology of Binary Images: Figures, Skeletons, Circulars (FIZMATLIT, Moscow, 2009) [Russian].

[35] P. D. Lebedev and A. A. Uspenskii, Construction of a nonsmooth solution to the time-optimal problem with a low order of smoothness of the target set boundary, Tr. Inst. Mat. Mekh. 25 (1), 108–119 (2019 [Russian]).

[36] A. A. Savyolov, Flat Curves: Systematics, Properties, Applications (Librokom, Moscow, 2010) [Russian].

[37] E. Specht, Packomania (2018). Available at www.packomania.com (accessed Aug. 13, 2020).