An Algorithm for Packing Circles of Two Types in a Fixed Size Container with Non-Euclidean Metric

Abstract

The paper deals with the problem of optimal packing of two sets of circles (2-D spheres) into a simply connected container. The number of circles is given. The radii of these circles are equal within each set, but, generally speaking, they differ between sets. There are two different statements of a such problem. The simplest one is when the circles of a larger radius are located first, and then smaller circles are packed into the gaps. Solving of a such problem, in fact, reduces to a two-fold solution of the equal circles packing problem. However, the procedure is complicated by the fact that in the second solution the container will be a multiply connected set. We consider a more complex formulation: it is required to maximize the radii of the circles when their ratio is fixed. The circle packing problem is usually studied in the case when the distance between points is Euclidean and even then belongs to the class of NP-hard problems. We assume that the distance is determined by means of some special metric, which, generally speaking, is not Euclidean. The special numerical algorithm is suggested and implemented. It based on optical-geometric approach, which is developed by the authors in recent years and previously used only for packing circles of equal radius. The results of computational experiment are presented and discussed.

Keywords

• circle packing problem
• unequal circles
• non-Euclidean space
• numerical algorithm
• computational experiment

Introduction

Packing problems constitute a set of NP-hard optimization problems, which appear in many fields of human activity such as industrial engineering, transport and infrastructural logistics, circular cutting, computer science [5, 6]. The circle packing problem has a long history, see [8, 16, 21]. The aim is to pack a certain number of circles, each one with a maximal radius (not necessary the same for each circle) inside a container. The shape of the container may be “simple” like a circle, a square, a rectangular, or, for example, consists of combination of line and arc segments.

In this paper we address the problem of packing two sets of circles in a simply connected container. There are two approaches that have been used in the literature. The first is an extension of the classical circle packing problem, where we continue packing smaller circles in the empty rest of the container after packing greater ones. Obviously, the density of the next package is always greater in comparison with the previous one. It was F.L. Toth, who in 1958 considered this statement and proved that when the plane is filled with circles of two different sizes, the gap space can not be less than 86.69% [25] (Chapter 6), [26].

The second approach is packing of circles with different sizes, when we fix the relation of radii of the circles. This problem is more popular than the first one and has been extensively considered in the literature.

Stoyan and Yaskov [20] present a mathematical model for the nonidentical circles packing in the form of nonlinear global optimization problem and solve it using a combination of branch-and-bound and the reduced gradient method. The results of packing of 100 circles are shown.

Wang et al. [27] propose an approved algorithm – the quasi-physical quasihuman algorithm, where the quasi-physical part is an analogy to the physical model in which a number of smooth cylinders are packed inside a container and a quasi-human strategy is then proposed to trigger a jump for a stuck object in order to get out of local minima. Zhang and Deng [29] generalize the model of [27] and use a hybrid approach consisting of simulated annealing to explore the neighborhood of the current solution, and tabu search to implement the jumps. Zeng et al. [28] propose the algorithm, which adapts the Tabu Search procedure of Iterated Tabu Search algorithms and proposes a Tabu Search and Variable Neighborhood Descent (TS-VND) procedure.

Pinter and Kampas [17] design numerical algorithms using Lipschitz Global Optimizer (LGO) software. In [5] the authors apply various global optimization techniques with a posteriori strategy that includes the rules of initial arrangement and swapping all pairs of adjacent sized circles. Lopez and Beasley [13] offer a heuristic algorithm that consist of optimization and improvement phases. For the first phase the formulation space search method with a mixed Cartesian/Polar formulation is used, and for the second one a swapping process aiming to improve the solution obtained in the first phase is suggested. In [14] FSS algorithm for the problem of packing unequal circles inside a fixed size circular container is presented. The survey of publications could be continued because there are a lot of notable publications. Some record numerical results are available on www.packomania.com [19].

Note that the most of known results are obtained for the case when covered areas or containers are subsets of the Euclidean plane or a multi-dimensional Euclidean space. In the case of a non-Euclidean metric, covering and packing problems are relatively poorly studied. Here we could mention the works by Coxeter [7] and Boroczky [3], which deal with congruent circles packing problems for multidimensional spaces of a constant curvature and McEliece and Rumsey [15], who use the Hamming Metric. Besides above, this problem was studied in a series of papers by Szirmai [22–24]. The circle packing problem with special non-Euclidean metric in the case of equal circles was considered in [11].

In this paper, we expand a technique proposed in [9, 10] for solving the problem of packing two sets of circles in a simply connected container when the distance between two points is defined as minimal time of moving from one of them to another. The suggested algorithm includes a random generation method for determining the initial positions of the circles centers; an optical-geometrical method based on the fundamental physical principles of Fermat and Huygens, which makes it possible to use the non-Euclidean metric [9]; K-means method for refinding the positions of the circles centers [1]. 1

Formulation

Let X is a metric space, P is closed simply connected set, Ci are congruent circles, si = (xi; yi), are centers of Ci, i = 1; :::; n + m. Let first n circles have radius R1 and other m have radius R2 = k1 R1, k 2 N. It is necessary to find vector s = (s1; :::; sn+m) 2 R2(n+m), which provides the packing of the given number of circles with maximum radius R1 (and R2 as well) in P .

The distance between the points of the space X is determined as follows [9]: ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 )

R1 ! max R2 = 1 k R1; k 2 N (si; sj )

2R1; 8i; j = 1; n; i 6= j (si; sj )

2R2; 8i; j = n + 1; n + m; i 6= j (si; sj )

R1 + R2; 8i = 1; n; 8j = n + 1; n + m

R1; 8i = 1; n

R2; 8j = n + 1; n + m si 2 P; 8i = 1; n + m Here @P is the boundary of the set P , (si; @P ) is the distance from a point to a closed set.

The objective, Eq. ( 2 ), maximizes the radius associated with the circles. Eq. ( 3 ) fixes the ratio of radii. Inequalities ( 4 )–( 6 ) ensure that no circles overlap (a; b) =

min G2G(a;b)

Z G

dG f (x; y) ; where G(a; b) is the set of all continuous curves, which belong X and connect the points a and b, 0 < f (x; y) is continuous function defined instantaneous speed of movement at every point of P .

Thus, we formulate the following problem: each other. Inequalities ( 7 )–( 9 ) are the constraints which ensure that every circle is fully inside the container.

Before we propose an algorithm, for any vector s define the sets Pi = fp 2 P : (p; si) (p; sq); i = 1; :::; n + mg ; where ( 10 ) 8 1; i; q = 1; :::; n or i; q = n + 1; :::; n + m = < k; i = n + 1; :::; n + m; q = 1; :::; n : k1 ; i = 1; :::; n; q = n + 1; :::; n + m : In the literature, if the set P . It’s obvious that P = 1 such sets are called Dirichlet cells [18] for points si on n+m S Pi.

i=1 2

Solution Method

In this section, the authors propose a heuristic method for solving problem ( 2 ),( 9 ), based on the analogy between the propagation of the light wave and finding the minimum of the functional integral ( 1 ). This analogy is a consequence of physical principles of Fermat and Huygens. The first principle says that the light in its movement chooses the route that requires to spend a minimum of time. The second one states that each point reached by the light wave, becomes a secondary light source. This approach is described more detail in [9, 10, 12].

The essence of the algorithm is as follows.

At first, we consistently separate the given set P into segments with respect to the randomly generated initial set of circles centers based on Voronoi diagrams. It’s required to initiate synchronously the light waves from the points si, i = 1; :::; n + m, and to find such points of P , which are simultaneously reached by two or more waves.

At second, we find the center of packed circle with maximum radius for each segment. It’s required to carried out the construction of the light wave front, started from the border @Pi for each Pi to the time when the front degenerate into a point.

Then we construct the segmentation for the new found centers.

Algorithm of Two Types Circles Packing 1. Randomly generate an initial solution s = (s1; :::; sn+m), which satisfies the constraint ( 9 ). The radii R1 and R2 are assumed to be zero. 2. The set P is divided into subsets Pi, i = 1; :::; n + m, according to the definition ( 10 ). To do this, we initiate light waves from points si by the authors’ algorithm proposed in [9]. Note, that because of unequal radii we have to deal with the “fast” and “slow” waves. It’s the main difference from [9]. 3. For each Pi, i = 1; :::; n, find the point si 2 Pi that For this we initiate the light waves propagating from the boundary of @Pi of every segment Pi in the inner area and construct the wave fronts until they converge at a point: (a) Boundary @Pi is approximated by the points Ak; k = 1; q. (b) At each point Ak, we construct a tangent and a normal vector directed to the interior of Pk. Then postponing along the normal vector a segment of length f (Ak) t, we obtain the points Bk of the new wave front. Here t is time step. (c) The Bezier curve is constructed using the points Bk.

Steps (a)–(c) are being carried out until the constructed front becomes a nonclosed line or a point.

If the constructed front is nonclosed line, then the solution is the “middle” of the line, namely the point the distance from which to the ends of line is the same.

If the constructed front consists of one point, then this point is the solution.

As a result, for each Pi, i = 1; :::; n+m, we find the coordinates of the packed circle center si and its maximum radius ri. 4. Calculate R1 = i=m1;i:n::;n ri and R2 = i=n+m1;:i:n:;n+m ri.

Steps 2-4 are repeated until the R1 (and R2 as well) increases, then vector s is memorized as a current solution of the problem ( 2 )–( 9 ) if it is greater than the maximum value of the previously found radii. 5. The counter of an initial solution generations Iter is incremented. If Iter becomes equal some preassigned value, then the algorithm is terminated.

Otherwise, go to step 1. 3

Numerical Experiment

Testing of the algorithm proposed in the previous section was carried out using the PC of the following configuration: Intel (R) Core i7-5500U (2.4 GHz, 8 GB RAM) and Windows 10 operating system. The algorithm is implemented in C# using the Visual Studio 2013.

Example 1. This example illustrates how the proposed in the previous section algorithm works in the case of the Euclidean metric f (x; y) 1. Here the radius of large circles is twice the radius of small ones. The number of circles is given and we maximize the radius. The number of random generations of initial positions is five. Fig. 1 shows the best solutions in Table 1. Here and further n is a number of large circles, m is a number of small circles, R is the best radius of large circles, D is density of packing, Reql and Deql is the radius of equal circles and density respectively given in [19], t is time of calculation. It is easy to see that the problem has an infinite set of solutions that can be obtained from the one shown in the fig. 1 using the rotation operator.

Here we can see that the radii of the big circles are expected to be greater than in the case of equal circles. As for the density, we can say that it is, as a rule, smaller than for equal circles. This is due to the presence of a strict condition on the ratio of radii ( 3 ). But for several cases (for example, 3 big and 3 small circles) density becomes grater than for equal circles, because small circles fill in the gaps left after packing big ones.

Example 2. This example considers the case when the metric is given by the formula ( 1 ), where f (x; y) = 0(1 + ky), 0; k are given constants (here 0 = 1; k = 0:1). This means that the speed of wave propagation increases linearly with the coordinate y. Borovskikh [4] proved that in this case the wave fronts also have the form of a circle, as in the Euclidean metric, but the source of the wave (the center of the circle) is displaced. Note that the circles located lower (see fig. 2) visually seem to be grater, however they have the same radii. Bold line shows circles of smaller radius. The computational domain has a size of 100x100 cu. Recall that the radius (R) here means the time of moving from center to the boundary of the circle. The computational results are presented in Table 2. Example 3. Here we construct f (x; y) by following rule.

(x 2:5)2+(y 2:5)2 a1(x; y) = 1+(x 2:5)2+(y 2:5)2 ; f1(x; y) =

(x 2:5)2+(y 7:5)2 a2(x; y) = 1+(x 2:5)2+(y 7:5)2 ; f2(x; y) =

(x 7:5)2+(y 2:5)2 a2(x; y) = 1+(x 7:5)2+(y 2:5)2 ; f3(x; y) =

(x 7:5)2+(y 7:5)2 a3(x; y) = 1+(x 7:5)2+(y 7:5)2 ; f4(x; y) = 0; a1(x; y) a1(x; y); 0; a2(x; y) a2(x; y); 0; a3(x; y) a3(x; y); 0; a4(x; y) a4(x; y); 0:8; 0:8; 0:8; 0:8; F (x; y) = f1(x; y) + f2(x; y) + f3(x; y) + f4(x; y); 8 0:4; 0 < F (x; y) < f (x; y) = F (x; y); : 0:8; F (x; y) = 0:

0:4; Such metrics are used in infrastructure logistics if one needs to locate several facilities on a hilly country or in the field of security [2]. Here speed of movement depends on the angle of ascent or descent. Therefore the wave fronts are strongly distorted.

The container in this case is a non-convex polygon. Radius of large circles is 3 times larger than the radius of small ones.

Fig. 3 shows the solutions associated with Table 3 in the case where the form of the wave fronts is unknown.

Note that, as in the previous example, in the given metric presented on Fig. 3 the thin “circles” have the same radius R and the bold “circles” have the radius R=3.

Tables 2 and 3 confirm the obvious fact: when the number of large circles does not change, the best radii decrease with increasing the number of small circles. However, the packing density does not depend on the change in the number of small circles and it wasn’t evident. Note, that the total time for solving the problem is relatively small. Optimal packing and covering problems are known to be a particular class of clasterization problems, as all points inside a circle enjoy the same obvious property: they are closer to the center of the respective circle, compared to the centers of the other circles in the covering. In other words, each a circle can be regarded as a cluster, described by its center and radius.

In this paper, we address a problem of optimal packing of two sets of circles (2-D spheres) into a simply connected container. The cardinality of these sets is prescribed, and the ratio of radii of circles of two collections is assumed to be fixed. The goal is to maximize the radii of the packed circles. In this formulation, the problem is rather complicated and, even if all the radii are equal to each other, belongs to the class of NP-hard problems.

We operate with a specific, not necessary Euclidean, distance function. The feature of this metric, arising in certain practical problems of logistics, is as follows: the physical distance is replaced by the time, required for reaching one point from another.

In our previous work [11], a computational algorithm was developed for optimal packing of circles with equal radii, based on an “optical-geometric approach”. Here a modification of this approach is proposed to take into account the features of the general problem. The approach employs a rather simple idea: circles are regarded as certain wave fronts; the smaller radius of a circle – the slower the wave’s expansion. Note that a practical implementation of this idea occurred to be quite technically laborious. Nevertheless, we managed to elaborate an efficient software implementation of the proposed algorithm.

A series of test cases for both Euclidean and a specific non-Euclidean metrics is implemented and analyzed. The results prove the applicability of the proposed approach.

Future efforts in this direction can be connected both with application to problems of logistics (for example, simultaneous placement of logistic centers of two types), and with a further extension of the mathematical formulation, for example, towards increasing a number of sets of packed circles with different radii.

Acknowledgements. The reported study was particulary funded by Russian Foundation of Basic Research according to the research projects No. 16-31-00356 and No. 16-06-00464. 22. Szirmai, J.: The optimal ball and horoball packings of the coxeter tilings in the hyperbolic 3-space. Beitr. Algebra Geom. 46( 2 ), 545–558 (2005) 23. Szirmai, J.: The optimal ball and horoball packings to the coxeter honeycombs in the hyperbolic d-space. Beitr. Algebra Geom. 48( 1 ), 35–47 (2007) 24. Szirmai, J.: A candidate for the densest packing with equal balls in thurston geometries. Beitr. Algebra Geom. 55( 2 ), 441–452 (2014) 25. Toth, F.: Lagerungen in der ebene auf der kugel und im raum (in German).

Springer-Velag, Berlin (1985) 26. Toth, F.: Densest packing of translates of the union of two circles. Discrete and

Computational Geometry 1, 307–314 (1986) 27. Wang, H., Huang, W., Zhang, Q., Xu, D.: An improved algorithm for the packing of unequal circles within a larger containing circle. European Journal of Operational Research 141( 2 ), 440–453 (2002) 28. Zeng, Z., Yu, X., He, K., Huang, W., Fu, Z.: Iterated tabu search and variable neighborhood descent for packing unequal circles into a circular container. European Journal of Operational Research 250( 2 ), 615–627 (2016) 29. Zhang, D., Deng, A.: An effective hybrid algorithm for the problem of packing circles into a larger containing circle. Computers & Operations Research 32( 8 ), 1941–1951 (2005)

References

1. Anil , K. , Richard , C. : Algorithms for clustering data . New Jersy: Prentice Hall ( 1988 )

2. Bashurov , V. , Filimonenkova , T. : Matematicheskie modeli bezopasnosti (in Russian) . Nauka, Novosibirsk ( 2009 )

3. Boroczky , K. : Packing of spheres in spaces of constant curvature . Acta Mathematica Academiae Scientiarum Hungarica 32 ( 3 ), 243 - 261 ( 1978 )

4. Borovskikh , A. : The two-dimensional eikonal equation . Siberian Mathematical Journal 47 ( 2 ), 813 - 834 ( 2006 )

5. Castilo , I. , Kampas , F. , Pinter , J.: Solving circle packing problems by global optimization: Numerical results and industrial applications . European Journal of Operational Research 191 ( 3 ), 786 - 802 ( 2008 )

6. Conway , J. , Sloane , N.: Sphere Packing . Lattices and Groups . Springer science and Business Media, New York ( 1999 )

7. Coxeter , H.S.M.: Arrangements of equal spheres in non-euclidean spaces . Acta Mathematica Academiae Scientiarum Hungarica 5 ( 3 ), 263 - 274 ( 1954 )

8. Hifi , M. , M'Hallah , R.: A literature review on circle and sphere packing problems: Models and methodologies . Advances in Operations Research 2009 , 1 - 22 ( 2009 )

9. Kazakov , A. , Lempert , A. : An approach to optimization in transport logistics . Automation and Remote Control 72 ( 7 ), 1398 - 1404 ( 2011 )

10. Kazakov , A. , Lempert , A. : On mathematical models for optimization problem of logistics infrastructure . International Journal of Artificial Intelligence 13 ( 1 ), 200 - 210 ( 2015 )

11. Kazakov , A. , Lempert , A. , Nguyen , H.: The problem of the optimal packing of the equal circles for special non-euclidean metric . Communications in Computer and Information Science 661 , 25 - 68 ( 2017 )

12. Lempert , A. , Kazakov , A. , Bukharov , D. : Mathematical model and program system for solving a problem of logistic object placement . Automation and Remote Control 76 ( 8 ), 1463 - 1470 ( 2015 )

13. Lopez , C. , Beasley , J.: Packing unequal circles using formulation space search . Computers and Operations Research 40 ( 5 ), 1276 - 1288 ( 2013 )

14. Lopez , C. , Beasley , J.: A formulation space search heuristic for packing unequal circles in a fixed size circular container . European Journal of Operational Research 251 ( 1 ), 64 - 73 ( 2016 )

15. McEliece , R. , Rumsey , H.: Sphere-packing in the hamming metric . Bull. American Math. Soc . 75 , 32 - 34 ( 1969 )

16. Peikert , R. , Wiirtz , M. , Monagan , C. , Groot , C. : Packing circles in a square: A review and new results . System Modelling and Optimization. Lecture Notes in Control and Information Sciences 180 , 45 - 54 ( 1992 )

17. Pinter , J. , Kampas , F. : Nonlinear optimization in mathematica with math optimizer professional . Mathematician Education and Research 10 ( 2 ), 1 - 18 ( 2005 )

18. Preparata , F. , Shamos , M. : Computational Geometry. An Introduction. SpringerVerlag , New York ( 1985 )

19. Specht , E.: Packomania. http://www.packomania.com/, accessed: 2015 -10-28

20. Stoyan , Y. , Yaskov , G.: Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints . International Transactions in Operational Research 5 ( 1 ), 45 - 57 ( 1998 )

21. Szabo , P. , Markot , M. , Csendes , T. , Specht , E. , Casado , L. : New approaches to circle packing in square with program codes . Springer US, New York ( 2007 )