9512.net

# Dense Packings of Congruent Circles in Rectangles with a Variable Aspect Ratio

arXiv:math/0405148v2 [math.MG] 17 May 2004

Dense Packings of Congruent Circles in Rectangles with a Variable Aspect Ratio

Boris D. Lubachevsky bdl@bell-labs.com Bell Laboratories 600 Mountain Avenue Murray Hill, New Jersey

Ronald Graham graham@ucsd.edu University of California at San Diego La Jolla, California

Abstract We use computational experiments to ?nd the rectangles of minimum area into which a given number n of non-overlapping congruent circles can be packed. No assumption is made on the shape of the rectangles. Most of the packings found have the usual regular square or hexagonal pattern. However, for 1495 values of n in the tested range n ≤ 5000, speci?cally, for n = 49, 61, 79, 97, 107, ...4999, we prove that the optimum cannot possibly be achieved by such regular arrangements. The evidence suggests that the limiting height-to-width √ ratio of rectangles containing an optimal hexagonal packing of circles tends to 2 ? 3 as n → ∞, if the limit exists. Key words: disk packings, rectangle, container design, hexagonal, square grid AMS subject classi?cation: primary 52C15, secondary 05B40, 90C59

1. Introduction Consider the task of ?nding the smallest area rectangular region that encloses a given number n of circular disks of equal diameter. The circles must not overlap with each other or extend outside the rectangle. The aspect ratio of the rectangle, i.e., the ratio of its height to width, is variable and subject to the area-minimizing choice as well as the positions of the circles inside the rectangle. Packing circles in a square has been the subject of many investigations [GL], [NO1], [NO2], [NO3]. Because the aspect ratio is not ?xed in our present problem, the solutions are typically di?erent from the dense packings in a square. For example, the density π/4 = 0.785... of the proved optimum (see [NO3]) for √packing 25 congruent circles in a square (see Figure 1.1a) can be increased to 25π/(26(2 + 3)) = 0.809..., if we let the rectangle assume its best aspect ratio (see Figure 1.1b). Our experiments o?er only three values of n for which 1

a

b
Figure 1.1: The best packings found for 25 circles a) in a square, and, b) in a rectangle with variable aspect ratio.

Figure 1.2: A 224-circle fragment of the packing with the highest density found in a long rectangle with a ?xed aspect ratio.

2

the dense packing in a square is also a solution to our present problem: n = 4, 9, and of course, n = 1. Similarly, dense packings in long rectangles with a ?xed aspect ratio usually do not yield solutions for our problem. According to a long-standing conjecture attributed to Molnar (see [F¨ uredi]), dense packings in long ?xed rectangles tend to form periodic up and down alternating triangular “teeth,” as in the example shown in Figure 1.2. We can usually increase the density of such packings by slightly changing the aspect ratio of the rectangle. The present problem has been occasionally mentioned among packing problems ; for example, Web enthusiasts have recently began discussing it. However, the problem was considered as early as in 1970 in [Ruda], where the optimum packings were determined for all n ≤ 8 and conjectured for 9 ≤ n ≤ 12. We learned about Ruda’s results after we performed our computations and made our conjectures. Fortunately, our conjectures restricted to the values n ≤ 12 agree with the results and conjectures in [Ruda]! It appears that the complexity of the proofs of optimality in the packing-circles-in-asquare problem increases exponentially with n; computer generated/assisted proofs of optimality of such packings do not reach n = 30 (see [NO3] ; proofs that do not utilize computers have not been found except for quite small values of n), while conjectures extend to n = 50 and even much larger values (see [NOR]). Similarly, it seems to be di?cult for the present problem to prove optimality for the con?gurations we ?nd. This paper describes an experimental approach, where good packings are obtained with the help of a computer. Some of these packings hopefully will be proved optimal in the future. At present, most of the statements about the packings made in this paper are only conjectures, except for a few which we explicitly claim as proven. For instance, we prove that the best packings found are better than any other in their class, e.g., that the packing of 79 circles with a monovacancy (see Figure 2.3a), while non-optimal, is better than any hexagonal or square grid packing of 79 circles without a monovacancy. Also, we prove that n = 11 is the smallest n for which a hexagonal packing as in Figure 2.1 is better than any square grid packing of n circles. 2. A priori expectations and questions about best packings Since it is well known that the hexagonal arrangement of congruent circles in the in?nite plane has the highest possible density, (see [Th], [Ft], [FG],[Oler]), before plunging into our experiments, we expected to obtain good ?nite packings by “carving” rectangular subsets out of this in?nite packing. It will be useful to classify here such ?nite arrangements. For that we will discuss packings in Figures 1.1b, 2.1, 2.2a, 2.2b, and 2.3a, irrespective of their optimality (which will be discussed in the following sections). For the purpose of exposition, we will pretend in this section that there are no holes in the arrangements in Figures 2.2b and 2.3a, that is, the question mark in the ?gures is covered with an additional circle of the common radius. Under such an assumption, the arrangement in Figure 2.3a consists of h = 5 alternating rows with w = 16 circles in each, a total of n = w × h = 80 circles. Arrangements as in Figures 1.1b, 2.1, 2.2a, and 2.2b, are obtained by depleting such w × h arrays of some circles along one side of the array. The ways of performing the depletion depend on the parity of h. 3

Figure 2.1: The best packing found for 11 circles in a rectangle.

a

? b B

A C δ

B c

A C

Figure 2.2: Packings of 49 circles in a rectangle: a) the best in the class of hexagonal packings, b) a best in the class of hexagonal packings with monovacancies (one of 17 equally dense packings with the hole), c) the best we found.

4

a

? B

A C δ

b

B

A C

Figure 2.3: Packings of 79 circles in a rectangle: a) a best in the class of hexagonal packings with possible monovacancies, and, b) the best we found.

b

c

a
Figure 2.4: Best packings found for 12 circles in a rectangle.

5

If h is even, then the depletion can be done in only one way by removing h/2 circles. Figure 1.1b presents an example with h = 2. The case of an odd h presents two possibilities: we can remove ?h/2? circles on a side as in the example of Figure 2.2b, or ?h/2? + 1 circles on a side as in the example of Figure 2.2a. Alternatively, one can consider rectangular square grid arrangements as candidates for the best packings, e.g., see those in Figure 2.4. The density of a square grid arrangement is ?xed at π/4 independent of n. When both sides √ h and w of the carved rectangle tend to in?nity, the hexagonal packing density tends √ to π/(2 3) which is the density of the hexagonal packing in the in?nite plane. Since π/(2 3) > π/4, one naturally wonders for which n the best hexagonal grid arrangement becomes better than the square grid arrangement. A natural question is whether or not both arrangements exhaust all possibilities for the best packing. In other words, does there exist an optimal packing of n disks in a rectangle such that it cannot be represented as being carved out by a rectangle from either square grid or hexagonal grid packing of the in?nite plane? 3. Results of compactor simulations To tackle the problem by computer, we developed a “compactor” simulation algorithm. The simulation begins by starting with a random initial con?guration with n circles lying inside a (large) rectangle without circle-circle overlaps. The starting con?guration is feasible but is usually rather sparse. Then the computer imitates a “compactor” with each side of the rectangle pressing against the circles, so that the circles are being forced towards each other until they “jam.” Possible circle-circle or circle-boundary con?icts are resolved using a simulation of a hard collision so that no overlaps occur during the process. The simulation for a particular n is repeated many times, with di?erent starting circle con?gurations. If the ?nal density in a run is larger than the record achieved thus far, it replaces this record. Eventually in this process, the record stops improving up to the level of accuracy induced by the double precision accuracy of the computer. The resulting packing now becomes a candidate for the optimal packing for this value of n. In this way we found that the square grid pattern with density π/4 supplies the optimum for n = 1, ..., 10, and that n = 11 is the smallest number of circles for which a density better √ than π/4 can be reached; the density of this packing is 11π/(16(1 + 3) = 0.790558.. The corresponding conjectured optimum pattern for n = 11 is shown in Figure 2.1. The pattern is hexagonal. For n = 12 and 13 the square grid pattern brie?y takes over as the experimental optimum again (see Figure 2.4 for the case of n = 12). Remarkably, Ruda [Ruda] proves that for n ≤ 8, the square-grid packings are optimal. His conjectures for 9 ≤ n ≤ 12 also agree with our ?ndings. Our simulation results show that for n ≥ 14, the best densities are larger than π/4. This statement is also easy to prove, considering examples of (not necessarily optimal) two-row hexagonal packings like that in Figure 1.1b for odd n = 2m + 1 > 14, or the ones with equal length rows for even n = 2m ≥ 14. Assuming the circles have radius 1, the following inequalities √ 2(m + 1)(2 + 3) < 4(2m + 1) (1)

6

a

b

Figure 3.1: Two equally dense best packings found for 15 circles in a rectangle. for n = 2m + 1 and (2m + 1)(2 + √

3) < 8m

(2)

for n = 2m have to be satis?ed. The left-hand sides in (1) and (2) are the areas of the enclosing rectangles for the two-row hexagonal packings, and the right-hand sides are the areas for the corresponding square grid packings. It is easily seen that all integers m ≥ 7 satisfy either inequality. These correspond to all integer values of n ≥ 14. A surprise awaited us at the value n = 15. We found two di?erent equally dense packings. One, shown in Figure 3.1a, is of the expected hexagonal type. However, the other, shown in Figure 3.1b, is not, nor can it be carved out of the square grid. It is easy to verify that two equally dense packings a and b of these types also exist for any n of the form n = 15 + 4k , k = 1, 2, 3, .... Packing a, such as that in Figure 3.1a, has two alternating rows, with one row one circle shorter than the other, and with the longer row consisting of w = 8 + 2k circles. Packing b, such as that in Figure 3.1b, has 4 rows, the longest row having w = 4 + k circles, three bottom rows alternate, the middle one having w ? 1 circles, and the 4th row of w circles stacked straight on the top (or on the bottom; these would produce the same con?guration). Our experiments suggest that for k = 1 and 4, i.e., for n = 19 and 31, these pairs of con?gurations might also be optimal; however, they are provably not optimal for other values of k > 0. The packings of pattern b for n = 15, 19, and 31, if they are proved to be optimal, answer positively the second question posed in Section 2. Thus, the optimal container for 15 bottles apparently can have two di?erent shapes, as can the optimal containers for 19 and 31 bottles! In an obvious way, more than one optimum container shape also exists for square grid packings of n circles if n is not a prime. See Figure 2.4 for the example of n = 12; there are three di?erent rectangles which are equally good and probably optimal for n = 12. Apparently, three is the maximum number of rectangular shapes, any number n of circles can optimally ?t in. It seems that for n = 4, 6, 8, 9, 10, 15, 19 and 31, there are exactly two shapes. For all other n tested, only one best 7

aspect ratio was found experimentally. Another packing surprise awaited us at n = 49. Figures 2.2a and 2.2b show two among several equivalent packings achieved in our simulation experiments. The con?guration a is hexagonal, while con?guration b contains a monovacancy, that is, a hole than can accommodate exactly one circle. Monovacancies in hexagonal arrays of congruent circles appear often in the simulation experiments for 14 ≤ n < 49 but only in packings of inferior quality, so that a better quality hexagonal packing without monovacancies could always be found. No higher density hexagonal packing without monovacancies was found for n = 49. Such large n already present substantial di?culties for our simulation procedure. The procedure failed to produce a packing which is better than those in Figures 2.2a and 2.2b. However, it is easy to prove that the density of a hexagonal packing in a rectangle with a monovacancy can be increased. For example, to improve the packing in Figure 2.2b we relocate circle B into the vacancy and then rearrange circles A and C along the side. This reduces the width of the rectangle by a small but positive δ as shown in Figure 2.2c, where √ √ δ = 2 ? 2 3 = 0.13879.. of the circle radius. The density of c is 49π/(2(1 + 3)(34 ? δ )) = 0.83200266... It is not known whether or not the resulting con?guration c can be further improved. However, using the exhaustive search we show (see next section) that the optimum packing for 49 circles in a rectangle, whatever it might be, cannot be purely hexagonal. The value n = 49 is apparently the smallest one for which neither square-grid nor perfect hexagonal pattern delivers the optimum. 4. Exhaustive search The simulation method becomes progressively slower for increasing n. However, by exercising the simulation for smaller n we are able to re?ne the idea of the class of packings which might deliver the optimum. We have chosen the class that consists of square grid and hexagonal packings and their hybrids; we also allow for monovacancies in con?gurations of the class, although these con?gurations are never optimal. We have extended our computing experiments to larger values of n using exhaustive search. For a given n, the method simply evaluates each candidate in the class by computing the area of the rectangle and selects the one with the smallest area. Note that for each n in this class, there are only a ?nite number of candidates. A general packing in the class (see Figure 4.1), consists of h + s rows and has d monovacancies. The h rows are hexagonally alternating, and the s rows are stacked directly on top of the previous row as in square grid packings. The longest row consists of w circles. Assuming all monovacancies are ?lled with circles, among the h hexagonal rows, h? rows consist of w ? 1 circles each, the remaining h ? h? rows consist of w circles each, and among the s square grid rows, s? rows consist of w ? 1 circles each, and the remaining s ? s? rows consist of w circles each. The number of circles in the con?guration is n = w (h + s) ? h? ? s? ? d (3)

Table 4.1 lists the best packings found of n circles in a rectangle with variable aspect ratio for n in the range 1 ≤ n ≤ 53, and Table 4.2 continues this list for 54 ≤ n ≤ 213. The 8

Figure 4.1: A “general case” member of the class of packings among which we search for the optimum; here w = 5, h = 5, h? = 2, s = 2, s? = 1, and d = 3. packings in Table 4.1 are obtained by the simulation procedure described in Section 3 and veri?ed by the exhaustive search. Most packings in Table 4.2 were generated only by the exhaustive search. An entry in either table consists of the n, followed by the set of integers which represent the parameters of the packing structure as explained above: w , the number of circles in the longest row, h, the number of rows arranged in a hexagonal alternating pattern, h? , the number of rows that consist of w ? 1 circles each, s, the number of rows, in addition to h rows, that are stacked in the square grid pattern. Column s is absent in Table 4.2, because, as explained in Section 3, no optimum packing found for n > 31 has s positive. Also, for any n, no optimum packing was found with s? > 0; thus, the s? column is omitted. In most packings presented in these two tables, the number of monovacancies d = 0, and so the d column is omitted. A few entries where monovacancies are possible are marked with stars. The non-starred entries describe the best packings found. The entries marked with stars cannot be optimal, as explained in Section 3. An improved packing for the marked case of 49 circles can be obtained as described in Section 3 (see Figure 2.2). The next marked case n = 61 is similar; Table 4.1 lists the variant a for it with h = 3 and h? = ?h/2? + 1 = 2. The following marked case is n = 79. Here too we improve the packing with the hole by relocating side circles. A, B , C , D , and E as shown in Figure 2.3, where the value of improvement δ is the same as in the case n = 49. This method of relocation applies to all marked cases in the tables when h is odd. For example, for the case of h = 5, when h? = 3 the relocation can be done as illustrated in Figure 4.3. This applies to the cases n = 97, 107, and 142 in Table 4.2. In all these cases, before using this method, we should replace listed in the tables variant that has h? = 9

n 1 2 3 4 5 6 7 8 9 10 11 12

13 14

w h 1 0 2 0 3 0 4 0 2 0 5 0 6 0 3 0 7 0 8 0 4 0 9 0 3 0 10 0 5 0 6 2 12 0 6 0 4 0 13 0 5 3

h? s 0 1 0 1 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 3 0 1 0 2 1 0 0 12 0 2 0 3 0 1 1 1

n 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

w h h? s 8 2 1 0 4 3 1 1 8 2 0 0 6 3 1 0 9 2 0 0 10 2 1 0 5 3 1 1 7 3 1 0 7 3 0 0 11 2 0 0 8 3 1 0 8 3 0 0 13 2 1 0 9 3 1 0 9 3 0 0 6 5 2 0 10 3 1 0 10 3 0 0 16 2 1 0 8 3 1 1 11 3 1 0

n 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 *49 50 51 52 53

w h h? 7 5 2 9 4 2 12 3 1 12 3 0 19 2 1 13 3 1 13 3 0 10 4 0 14 3 1 11 4 2 9 5 2 15 3 1 15 3 0 12 4 2 16 3 1 10 5 2 17 3 2 17 3 1 17 3 0 13 4 0 11 5 2

s 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Table 4.1: Packings of n circles in a rectangle for 1 ≤ n ≤ 53 with w circles in a row, h hexagonal rows, h? of which consist of w ? 1 circles each, and s square grid rows of w circles each. Except for the case n = 49 marked with a star, all packings are the best we could ?nd.

10

?h/2? = 2 with the variant that has h? = ?h/2? + 1 = 3. This would produce a con?guration with the pattern of the side as in Figure 4.3a. We would then improve this con?guration by relocating circles A, B , C , D , and E to yield a con?guration as in Figure 4.3b. The value √ √ √ of the improvement here is δ = 2 ? 0.5 3 ? 31/4 (2 3 ? 1)/(2 4 ? 3) = 0.05728... of the circle radius. A similar method works for even h. Sometimes during these improvements, some circles become the so-called rattlers, i.e., they become free to move and hit their neighbors, like the two unshaded circles in Figure 2.3. For glass bottles tightly packed in an empty box, packings with rattlers should de?nitely be avoided even though the box area was minimal! The case n = 79 and several others are marked in Table 4.2 with two stars to signify that the packing not only may contain a monovacancy, but in fact, it must: any hexagonal packing of n circles without a monovacancy is provably worse than the one represented in the table when n is marked with two stars. All such cases in the table also happen to have h? = 0. Also, a double-star marked entry in Table 4.2 always has a discrepancy between the n computed from the parameters of the packing structure using (3),(here it would be n = wh), and actual n. In all the other cases, the n computed from the packing structure parameters using (3) will always match the correct n because there are no monovacancies. However, no entry without a monovacancy is possible in the double-star marked cases. Another observation: an entry n + 1 that follows an entry n marked by one or two stars, always has the same w and h, and hence its packing ?ts in the same rectangle as that of the entry n. 5. Best packings found for larger n The exhaustive search procedure of Section 4 produces the best packings in the class de?ned in Section 4 for values of n on the order of several thousands. The features we observed for n ≤ 213 hold until n = 317. Namely, only one best size rectangle exists for each n. Most of the best packings in the search class are perfectly hexagonal and unique for their n. Each such packing can be described by the set w , h, and h? , with the latter parameter taking on up to three possible values: if h is even if h is odd then then h? = 0 or h? = 0 or h? = h/2 h? = ?h/2? or h? = ?h/2? + 1 (4)

A few exceptional cases have a single monovacancy. These are similar to the one-star marked cases with odd h and with two options for h? (the choice of the option de?nes the presence or absence of the vacancy), or they are similar to the two-star marked cases with h? = 0. The case n = 317 deviates from this pattern. Here, the best packing in the class has parameters w = 27, h = 12, h? = 6, and d = 1. Unlike the one-star marked cases, h is even, and unlike the two-star marked cases, h? is non-zero. Such a new type of packing recurs with one hole for n = 334 (w = 34, h = 10, and h? = 5) and then for n = 393 (w = 40, h = 10, and h? = 5), but in the latter case with two monovacancies. In other words, the best possible packing for 393 circles in a rectangle in the class of hexagonal packings with possible monovacancies must have two of them. 11

n 54 55 56 57 58 59 60 *61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 **79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

w h h? 14 4 2 11 5 0 19 3 1 19 3 0 12 5 2 20 3 1 9 7 3 21 3 2 21 3 1 13 5 2 16 4 0 22 3 1 17 4 2 10 7 3 14 5 2 12 6 3 14 5 0 24 3 1 18 4 0 15 5 2 11 7 3 15 5 0 19 4 0 26 3 1 16 5 2 16 5 0 16 5 0 12 7 3 21 4 2 17 5 2 14 6 0 17 5 0 22 4 2 15 6 3 18 5 2 30 3 1 18 5 0 13 7 0 23 4 0 19 5 2

n 94 95 96 *97 98 99 100 101 102 103 104 105 106 *107 108 109 110 111 112 113 114 115 116 117 118 119 120 *121 122 123 124 125 126 127 128 129 130 131 132 133

w h 24 4 14 7 16 6 20 5 20 5 17 6 20 5 34 3 15 7 21 5 12 9 18 6 27 4 22 5 22 5 16 7 22 5 19 6 16 7 23 5 19 6 23 5 17 7 20 6 24 5 17 7 20 6 14 9 14 9 18 7 16 8 25 5 21 6 12 11 26 5 22 6 19 7 15 9 22 6 27 5

h? 2 3 0 3 2 3 0 1 3 2 4 3 2 3 2 3 3 3 0 2 0 0 3 3 2 0 0 5 4 3 4 0 0 5 2 3 3 4 0 2

n 134 135 136 137 138 *139 140 141 *142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 *157 158 159 160 161 162 163 164 165 *166 167 168 169 170 171 172 173

w h h? 34 4 2 23 6 3 17 8 0 20 7 3 28 5 2 16 9 5 16 9 4 24 6 3 29 5 3 29 5 2 21 7 3 29 5 0 37 4 2 21 7 0 30 5 2 17 9 4 25 6 0 22 7 3 19 8 0 31 5 2 22 7 0 31 5 0 20 8 4 23 7 4 23 7 3 27 6 3 20 8 0 23 7 0 27 6 0 33 5 2 21 8 4 24 7 3 19 9 5 19 9 4 34 5 2 13 13 0 17 10 0 16 11 5 25 7 3 35 5 2

n 174 175 176 177 178 179 180 **181 182 183 184 185 186 187 188 189 190 **191 192 193 194 195 196 **197 198 *199 200 201 202 203 204 205 *206 207 208 209 210 *211 212 213

w 29 25 20 30 36 26 23 26 26 37 23 21 27 17 24 27 19 24 24 28 22 20 25 22 22 29 29 34 16 23 19 21 30 30 26 19 30 24 24 36

h h? 6 0 7 0 9 4 6 3 5 2 7 3 8 4 7 0 7 0 5 2 8 0 9 4 7 3 11 0 8 4 7 0 10 0 8 0 8 0 7 3 9 3 10 5 8 4 9 0 9 0 7 4 7 3 6 3 13 6 9 4 11 5 10 5 7 4 7 3 8 0 11 0 7 0 9 5 9 4 6 3

Table 4.2: Packings of n circles in a rectangle for 54 ≤ n ≤ 213 with w circles in a row, h hexagonal rows, h? of which consist of w ? 1 circles each. Except for the cases marked with stars, all packings are the best we could ?nd. 12

n(i)
5000

4000

3000

2000

1000

0

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 500 1000

i

0

1500

Figure 4.2: Numbers of circles n(i) for which the optimum packing in a rectangle is not perfectly hexagonal for 49 ≤ n(i) ≤ 5000 plotted versus the rank i.

13

δ A B a ? D E C b C A B D E

Figure 4.3: Improving a packing with a monovacancy when h = 5, h? = 2: a) an original hexagonal packing with a monovacancy, b) the transformed packing.

14

With two holes, we have more freedom to improve the quality of the packing than having just one hole. Several ways are possible, including combining the ones described before for cases of smaller n. Same as for the other packings with monovacancies, the optimal packing for n = 393 is not known, but the exhaustive search in our experiments proves that it cannot be a hexagonal packing. Naturally, the best packing (in the search class) of n = 394 circles also has parameters w = 40, h = 10, h? = 5 and d = 1, i.e., a single monovacancy. The same rectangle also accommodates the best packing in the class of n = 395 circles, with the same w = 40, h = 10, h? = 5. Since the latter packing is without holes, it is conceivable that it is optimal. The next outstanding case is n = 411 where w = 38, h = 11, h? = 6, and d = 1. This is the smallest n where the h is odd and h? = ?h/2? + 1, that is, the packing looks like the one in Figure 2.2a, but unlike the latter it has a hole. An equivalent packing that looks like the one in Figure 2.2b, where h? = ?h/2? = 5 also exists, but unlike the latter it has not one but two holes. For next value n = 412, we have a standard one-star marked situation with the same sizes of the rectangle, i.e., w = 38, h = 11 and h? = ?h/2? = 5 for the variant with one hole and h? = ?h/2? + 1 = 6 for the variant without holes. The smallest n for which as many as three monovacancies exist in the best packing in the class is n = 717. The corresponding packing parameters are w = 48, h = 15, h? = 0 and no hexagonal packing with a smaller number of holes can be better or even as good as this packing. Similarly, with four monovacancies, the smallest n is n = 2732 (w = 86, h = 32, and h? = 16), and for ?ve monovacancies, n = 2776 is the smallest (w = 103, h = 27, and h? = 0). No optimum packing in the class for n ≤ 5000 has six or more monovacancies. In all, we found 1495 values of n on the interval 1 ≤ n ≤ 5000 for which the best packing in the class must or can have monovacancies. As explained above, for each such n the best packing provably cannot be of a pure square-grid or hexagonal pattern. It is not proven though, but we believe it to be also true, that those 1495 values of n are all such irregular values among the considered 5000 values. The chance to encounter such an irregular n seems to increase with n. For example, here are all the experimentally found irregular values of n among 100 consecutive values on the intervals 401 + 1000k ≤ n ≤ 500 + 1000k for k = 0, 1, 2, 3, 4: 17 values for 401 ≤ n ≤ 500: 409, 411, 412, 421, 422, 433, 439, 453, 454, 461, 463, 467, 471, 478, 487, 489, 499. 24 values for 1401 ≤ n ≤ 1500: 1401, 1402, 1405, 1409, 1412, 1414, 1423, 1427, 1429, 1434, 1446, 1447, 1451, 1453, 1457, 1459, 1466, 1468, 1477, 1483, 1486, 1487, 1489, 1497. 33 values for 2401 ≤ n ≤ 2500: 2401, 2402, 2406, 2411, 2419, 2421, 2423, 2428, 2429, 2435, 2437, 2439, 2441, 2443, 2446, 2452, 2454, 2455, 2456, 2458, 2462, 2467, 2469, 2474, 2476, 2477, 2479, 2481, 2487, 2491, 2493, 2495, 2497. 33 values for 3401 ≤ n ≤ 3500: 3407, 3409, 3411, 3412, 3414, 3415, 3418, 3421, 3425, 3428, 3431, 3433, 3436, 3442, 3446 3447, 3453, 3455, 3459, 3461, 3464, 3467, 3469, 3473, 3476, 3479, 3481, 3487, 3489, 3490, 3493, 3494, 3499. 38 values for 4401 ≤ n ≤ 4500: 15

4401, 4404, 4405, 4409, 4411, 4414, 4417, 4419, 4421, 4426, 4430, 4434, 4436, 4438, 4441, 4443, 4447, 4450, 4453, 4456, 4457, 4458, 4461, 4462, 4467, 4468, 4474, 4476, 4479, 4483, 4486, 4487, 4491, 4492, 4493, 4495, 4497, 4499. Figure 4.2 represents these 1495 irregular values n(i), 1 ≤ n(i) ≤ 5000, beginning with n(1) = 49 and ending with n(1495) = 4999, by plotting points {abscissa = i, ordinate = n(i)}. 6. The optimum aspect ratio for large n Figure 6.1 contains for each n, a data point with coordinates (abscissa = n, ordinate = best aspect ratio found for this n). All n ≤ 5000 are represented with the exception of a few n where the best packings found are of the square grid type. Also, the hybrid packings like those in Figure 3.1b are excluded. In this way we assure the uniqueness of the best aspect ratio for each n represented. The aspect ratios for the best packings in the search class are described in Section 4. The changes to the aspect ratios are due to the δ shrinkages of the rectangles in those cases with monovacancies, such as those in Figures 2.2, 2.3, and 4.3. Presumably these are small in number and should not be noticeable in Figure 6.1. The data points tend to form patterns of descending and ascending “threads.” To examine the threads in detail, a rectangular box which is close to the y -axis in Figure 6.1 is magni?ed and represented in Figure 6.2. All data points present in the box can be found in Tables 4.1 and 4.2. The steep downward threads correspond to con?gurations with ?xed height, and with widths increasing by 1 from one point to the next as we move down the thread. Each such thread eventually terminates in either direction which means that the optimum rectangle cannot be too ?at or too tall. The less steep upward and downward threads (they are dotted) correspond to sequences (w, h), where from one point to the next w increases by 3 or 6 and h increases by 1 or 2, respectively. To compute the optimum aspect ratio of the rectangle that encloses the optimum packing for large n, we analyze the area wasted along the √ rectangle sides. Note that in the in?nite hexagonal packing, the uncovered area is s = 3 ? π/2 per each π/2 of the covered area. This is obvious from examining a single triangle XY Z in Figure 6.3 and observing that the entire in?nite packing is composed of such triangles. The waste s here is the √ area of the central triangle formed by three circular arcs and it is equal to the full area 3 of triangle XY Z (assuming circle radius is 1) minus π/2, which is the total area of the three π/6 sectors covered. (By the way, we remind the reader that the density of the in?nite hexagonal packing √ √ is ( 3 ? s)/(π/2) = π/(2 3) = 0.90689968....) The structure of the uncovered area in the in?nite hexagonal packing can be also understood if we think of each covered circle bringing with it two curved uncovered triangles s, those adjacent to this circle on its right-hand side. With such bookkeeping, each triangle s will be counted exactly once. We conjecture that these two triangles s per each circle is the unavoidable, i.e., ?xed, waste in any ?nite hexagonal packing carved out by a rectangle. 16

0.8

0.6

aspect ratio 0.4

2?√ ?3 0.2

0

0

1000

2000 3000 number of circles packed

4000

5000

Figure 6.1: Values of the aspect ratio for optimal hexagonal packings. 17

. .. . 42 ..

.. . .

24

. .. .

130
. . .. ....

96
.... .. . . . 68 . .. .. ...... .. . .. . ......

.99 .. .. .. ..

.. . .. .. ..

.. . .. .. ..

.. .. .. . ..

70
..... 26 ..... ..... ..... ..

.. .. .. .. .. . .. .. .. 137 . .. . .. ..

.. .. .. . .. . .. ..

.. 180

46.. .. .. .. .. .. .. ..

.. .. .. . .. ... ...

184
... ... ... ... ... ... ... . .... .... .... .... .... .... .... .... 105 .... . .. ...... . .. ..... ..... . ...... 144 .. ... .... .. 188

73

..... ... .. . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . .. . . . . .. . . . . . . .. . . .. . . . .. . . . . . . .. . . . .. . . . . . . .. . . . .. . . .. . . . . . . .. .147 .. 191192 . . ... . .... . ... .. ... . ... .. ... .. ... . ... .. ...75 27 .. 196 ...... . ..... .... .... ..... . ..... ...... .. ... .... ..... .... .... ..... .... .... ....151 . .. ...111 . . ... .. . . ... .. ... ... . . .. .. . . . . . . . .78 ... ... ... .. .. ... .. ... .. 114 .. .. .. .. .. .. .. .. .. .. .. .. ........ .. ... .. ... .. .. .. .. .. .. ... . . . . . . . .117 . .. 154 ... .. ... ... ... .. .. . 157158 .. .. .. .. 161 .. .. .. ..

..... 29

. ...... .. ......

..... .. .

........

30

.. . .. .

.. . . ...

. .. .

.. ..

. 52

..... ......

... ... .

.. .. .. 80 ... .. . . .79

.. .. .. .. .. .. ..

. .. 32

..

.. . ..

...

..

.. . ..

... .. . . 54 . ..

.....

. . .. .

...

.... .... ... . .83 . . .. . . ... .. .. 85

. .. ... .

.. .. .. .. .. .. .. .. .. . .. 120 ... .. ..

.. .. .. .. ..

165

88 90 93

126 129 132 135

172 175 179 181182

Figure 6.2: A box selected in Figure 6.1 magni?ed. Each data point in Figure 6.1 is replaced here with the corresponding number of circles.

18

Y s/2 s π/2 s s/2 B π/4 s π/4 A D C X π/6 π/6 s π/6 Z

Figure 6.3: Calculation of the waste area adjacent to the sides of the rectangle. There will be additional, i.e., variable, waste along the rectangle sides and we are trying to minimize this variable waste. Along the bottom and top sides, for each 2 units of length, like the side AD of rectangle ABCD in Figure 6.3, the additional waste is the area of rectangle ABCD minus two covered quarter-circle areas and minus s. This s represents one of the two curved triangles attached to the right-hand side of the circle with the center at B and as an unavoidable waste should not be included. Hence √ the waste per unit length of the top and bottom sides is a = (2 ? π/2 ? s)/2 = (2 ? 3)/2. √ The waste along the left- or right-hand sides per two alternating rows, i.e., per 2 3 units of length, is the area of the semicircle that is cut in half by the side plus or minus additional area depending on the side. Along the left-hand side, all additional uncovered area is additional waste, since we assume that the curved triangles s are attached to the right-hand side of the covered circles. The addition consists of two triangles √ s and two halves of triangles s/2 as shown in Figure 6.3. The left-hand side waste per 2 3 of length is thus π/2 + 3s. Along the right-hand side we subtract from the area of the semicircle the outstanding two half triangles √ s/2 because these are necessary in the in?nite packing. The right-hand side waste per 2 3 units of length is √ thus π/2 ? s. Averaging this for both sides √ and dividing by 2 3, we have b = (π/2 + s)/(2 3) = 1/2 as the additional waste per unit length of left-hand or right-hand √ sides. Now we should take a/b = 2 ? 3 as the ratio of height over width that yields the optimal balance between the waste along the sides of the enclosing rectangle and hence the minimum 19

area. Figure 6.1 includes a horizontal line at the level of the aspect ratio 2 ? 7. Concluding remarks

3.

As pointed out in the beginning of the paper, we hope that these computational results will lead to proofs of optimality for larger (or even in?nite classes of) n. Our experiments suggest that the frequency of occurrence of non-hexagonal best packings increases with n. It is not clear whether or not the frequency has a limit as n → ∞ and if it has, whether of not this limit is smaller than 1. While it is not easy to ?nd small n ≥ 14 for which the best packing is not perfectly hexagonal, it might be more di?cult to ?nd large n for which the best packing is perfectly hexagonal. Do there exist in?nitely many n, for which the densest packing of n circles in a rectangle is hexagonal? 1 A related phenomenon is conjectured to hold for n = N (k ) of the form N (k ) = 2 (ak + 1)(bk + 1) where ak and bk are given by: a1 = 1, a2 = 3, ak+2 = 4ak+1 ? ak
k are actually (alternate) so that, N (2) = 12, N (3) = 120, N (4) = 1512, etc. The fractions a bk 1 √ convergents to 3 , and it has been conjectured by Nurmela et al. [NOR] that for these n, a “nearly” hexagonal packing of n circles in a square they √ describe is in fact optimal. In our case, one should seek alternate convergents to 3 + 3/2 which yields sequences ak and bk given by:

b1 = 1, b2 = 5, bk+2 = 4bk+1 ? bk

ak = 2vk+1 ? vk , bk = 2vk , where v0 = 0, v1 = 1, vk+2 = 4vk+1 ? vk , k = 2, 3, ... Thus, (a1 , b1 ) = (7, 2), (a2 , b2 ) = (26, 8), (a3 , b3 ) = (97, 30).... so that N (2) = 208, N (3) = 2910, etc. No such N (k ) for k = 2, 3, ... is indeed found to be irregular in our experiments. The best packing found experimentally for such an N (k ) has h = bk alternating rows of full length w = ak with h? = 0, s = 0, in the notation of Section 4 and Tables 4.1 and 4.2. References [Ft] [FG] L. Fejes-Toth, Lagerungen in der Ebene, auf der Kugel und im Raum, SpringerVerlag, Berlin, 1953, 197 pp. J. H. Folkman and R. L. Graham, A packing inequality for compact convex subsets of the plane, Canad. Math. Bull. 12 (1969), 745–752.

20

[F¨ uredi] [GL] [L] [NO1] [NO2]

Z. F¨ uredi, The densest packing of equal circles into a parallel strip. Discr. Comp. Geom. 6 (1991), no. 2, 95–106. R. .L. Graham and B. D. Lubachevsky, Repeated Patterns of Dense Packings of Equal Disks in a Square, Electr. J. Combin. 3(1) (1996), #R16. B. D. Lubachevsky, How to simulate billiards and similar systems, J. Comp. Phys. 94 (1991), 255–283. ¨ K. J. Nurmela and P. R. J. Osterg? ard, Packing up to 50 equal circles in a square, Discr. Comp. Geom. 18 (1997), 111-120. ¨ K. J. Nurmela and P. R. J. Osterg? ard, Optimal Packings of Equal Circles in na Square, in: Combinatorics, Graph Theory, and Algorithms, Vol. II, Y. Alavi, D.R. Lick, and Schwenk (eds.), New Issues Press, Kalamazoo 1999 ¨ K. J. Nurmela and P. R. J. Osterg? ard, More optimal packings of equal circles in a square, Discr. Comp. Geom. 22 (1999), 439-457. ¨ K. J. Nurmela, P. R. J. Osterg? ard and R. aus dem Spring, Asymptotic behavior of optimal circle packings in a square, Canad. Math. Bull. 42 (1999), 380-385. N. Oler, A ?nite packing problem, Canad. Math. Bull. 4 (1961), 153-155. M. Ruda, The packing of circles in rectangles. (Hungarian. English summary) Magyar Tud. Akad. Mat. Fiz. Tud. Oszt., K¨ ozl., 19 (1970), 73–87. ¨ A. Thue, Uber die dichteste Zussamenstellung von kongruenten Kreisen in einer Ebene, Christiania Vid. Selsk. Skr. no. 1 (1910), 3-9.

[NO3] [NOR] [Oler] [Ruda] [Th]

21

...of Congruent Circles in Rectangles with a Variable Aspect ....unkown
Dense Packings of Congruent Circles in Rectangles with a Variable Aspect Ratio Boris D. Lubachevsky bdl@bell-labs.com Bell Laboratories 600 Mountain Avenue...
Why Hard Disks Pack Easier_图文.pdf
R. J. Ostergard, Dense packings of congruent circles in a circle, Discrete Mathematics, 181 (1998), 139-154. G70] M. Goldberg, The packing of ...
Dense packings of congruent circles in a circle.unkown
accepted 2 December 1996 Abstract The problem of finding packings of congruent circles in a circle, or, equivalently, of spreading points in a circle,...
...shown consists of a rectangle and two congruent circles. ....unkown
5. The figure shown consists of a rectangle and two congruent circles. If the area of the rectangle is 1250 square feet, what is the radius of one...
Representing homomorphisms of distributive lattices as ....unkown
Let be a {0, 1}-homomorphism of a finite distributive lattice D into the congruence lattice Con L of a rectangular (whence finite, planar, and...
Packing Rectangles with Congruent Polyominoes.unkown
TA972730 Packing Rectangles with Congruent Polyominoes William Rex Marshall 20 Albion Street, Shiel Hill, Dunedin, New Zealand Communicated by the Managing ...
...in (Conjectured) Densest Packings of Congruent Circles on ....unkown
(Conjectured) Densest Packings of Congruent Circles on a Sphere James Budden...dense packings, of which the best known at any point in time are ...
...into combinations of congruent triangles or rectangles and....unkown
H4XHVWLRQV ([DPSOH Each of the following four large congruent squares is subdivided into combinations of congruent triangles or rectangles and is ...
...of the sides of five congruent rectangles is labeled with ....unkown
sides of five congruent rectangles is labeled with an integer, as shown ...How many circles in the plane of R have a diameter both of whose ...
...proven using only the area of a rectangle and congruent ....unkown
Areas Quite a few ancient and famous theorems can be proven using only the area of a rectangle and congruent triangles. (1) Area(ABCD) = 10 cm2. ...
A parallelogram in which all four angles are congruent is a ....unkown
Definition: Rectangle A rectangle is a parallelogram in which all four angles are congruent. AB DC A parallelogram in which all four angles are congruent...
Figure HIJK is a rectangle. Name all the pairs of congruent ....unkown
Name all the pairs of congruent segments. Solution Since HIJK is a rectangle, it is also a parallelogram. By Property 1, HI JK and HK IJ...
Proving that if a parallelogram has congruent diagonals it ....unkown
Proving that if a parallelogram has congruent diagonals it must be a rectangle. Opp Sides of Parall. Th SSS Diag. bisect each other 12 1 + 2=180 ...
...averages over congruent rectangular plots that like in a ....unkown
Computation of spatial covariance matrices for data on rectangles Author David...Observations are averages over congruent rectangular plots that like in a ...
...averages over congruent rectangular plots that like in a ....unkown
Computation of Spatial Covariance Matrices for Data on Rectangles Author David...Observations are averages over congruent rectangular plots that like in a ...
...averages over congruent rectangular plots that like in a ....unkown
Computation of spatial covariance matrices for data on rectangles Author David...Observations are averages over congruent rectangular plots that like in a ...
...is a rectangle if and only if the diagonals are congruent.....unkown
Problems 2.4 and 2.5 Problem 2.4 Prove that a parallelogram ABCD is a rectangle if and only if the diagonals are congruent. Proof: Assumptions: ABCD is...
Regular packing of congruent polygons on the rectangular sheet.unkown
(dense double lattice) packing of congruent ...nonempty circle and having a piecewise linear ...aspects of the problem of optimal packing of the...
Optimal packings of congruent circles on spheres and flat tori.unkown
. . . . . 1 Optimal packings of congruent circles on spheres and flat tori 14:00 14:50 Alexey Glazyrin (Univ. of Texas at Brownsville ...
P Q Congruent Diagonals: The diagonals of a rectangle S R are....unkown
Properties of Rectangles, Rhombuses, and Squares One property of the ...Q R 2QU = QS Diagonals of 14 ft U a parallelogram are congruent QS =...