-- Packing unit circles in squares: new results
in [Math]
|
Prev: Delayed differential equation
Next: Ordered computation of eigenvalues from good initial estimates, without explicit sorting
From: David W. Cantrell on 20 Jun 2010 14:27 A small update about (rhombic, column-shift) hybrid packings is given. And a slightly improved packing for N = 250 is presented. -------------------------------------------------------------------------- Packomania now shows all hybrid packings previously mentioned here. And it also shows my presumably optimized hybrid packings (with just one column appended to the rhombic part) for N = 1818, 1236, 2126 and 2512; see <http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html> if interested. Another presumably optimized packing with one appended column is N = 6091, with side length 146.021168628... (The packing currently shown at Packomania has s = 146.021196...) But I don't know if my packing for N = 6091 will appear at Packomania because my data was computed using only machine precision. (Why didn't I use higher precision? Well, there was a system of 11882 quadratic equations to be solved...) In any event, my packing is shown at <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs6091sq.gif>. Since there are so many circles in that image, it may be hard to see exactly what's going on. But this packing is of _exactly_ the same sort as N = 493 <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs493sq.gif> and it's easy to see what's going on there. (Note in particular that, in each of these packings, the unit circle near the lower right corner of the square does not touch its right side.) Some hybrid packings having two or three appended columns will be sent to Packomania soon and will probably appear there in a day or so: N = 1308, 2614, 2718 and 9899. --------------------------------------------------------------------- N = 250 s = 30.41703105674489872839... 572 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs250sq.gif> (N.B. Some of the circles are very close together without touching. This makes me suspect that, when this new packing is eventually shown at Packomania, the number of contacts indicated there might not be correct, being higher than 572.) The best packing previously known has side length s = 30.417031056761... and 564 contacts. --------------------------------------------------------------------- David W. Cantrell
From: David W. Cantrell on 22 Jun 2010 21:28 The Triangle-Shift Family Part 1 -------------------------------------------------------------------------- A new family of packings is presented. Importantly, it fills a conspicuous void in families containing highly dense packings. -------------------------------------------------------------------------- Rhombic packings (including grid packings), such as the optimal packings for N = 18 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq18.html> and N = 137 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq137.html>, are associated with fractions p/q which underestimate sqrt(3). Column-shift packings, such as the optimal packing for N = 20 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq20.html>, are associated with fractions p/q, having p _odd_, which overestimate sqrt(3). In both of those families, packings tend to be denser the closer that p/q is to sqrt(3). Surely something special must also happen when p/q slightly overestimates sqrt(3) and p is _even_. But what, exactly? Part of the problem in answering that question lies in the fact that the archetype for the new family is more complicated than the archetypes for the rhombic and column-shift families. The name of the new family is the triangle-shift family for reasons that will become evident soon. One could choose to think of the column- and triangle-shift families as being two subfamilies comprising a larger "shift" family, associated with fractions p/q which overestimate sqrt(3). -------------------------------------------------------------------------- As an example, we now show, in three stages, how to produce an archetypal triangle-shift packing for N = 68. Stage 1: Single hexagonal lattice Notice that, taking p = 14 and q = 8, p/q overestimates sqrt(3). We will therefore be able to pack N = ceiling((p + 1)(q + 1)/2) = 68 unit circles in a square of side length s_shl = p + 2 = 16 by simply having all the circles in a single hexagonal lattice, as shown in the left figure at <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circs68sqSimple.gif>. Of course, this means that s_shl = 16 is an upper bound for the side length s of the optimal packing for N = 68. Surprisingly, calculating the upper bound for s based on Theorem 10.1 in NACPS [_New Approaches to Circle Packing in a Square_, P.G. Szabo et al. (Springer, 2007)], we obtain 3 (4 + sqrt(3)) = 17.196... and, using a trivial method mentioned previously in this thread, that bound can be improved to 218/13 = 16.769... But obviously, compared to either of those, the single-hexagonal-lattice packing for N = 68, although utterly trivial, provides a substantially tighter upper bound! Stage 2: Triangle & trapezoid We can always do better than a single-hexagonal-lattice packing. Referring again to the left figure at the above link, note that extra space is available to the right of the hexagonal lattice. One way to take advantage of that extra space is to shift a large trapezoidal hexagonal-lattice group down and to the right, as shown in the right figure. In general, we will then have a packing consisting of a large right-triangular hexagonal-lattice group, labelled A, which touches the left and bottom sides of the square, and a large trapezoidal hexagonal-lattice group, which touches A and the right side of the square. Adjusting the side length s_t&t so that the trapezoidal group also touches the top side of the square, we obtain s_t&t = (p + sqrt(3)q + 2 + sqrt(8 - (p - sqrt(3)q - 2)^2))/2 in general. With p = 14 and q = 8, this gives s_t&t = 8 + 4 sqrt(3) + sqrt(48 sqrt(3) - 82) = 15.99517... as an upper bound for the side length s of the optimal packing for N = 68. Of course, this upper bound is tighter than that obtained from the single-hexagonal-lattice packing. Stage 3: Triangle-shift And we can always do better still than a triangle-&-trapezoid packing. Referring to the right figure at the above link, note that extra space is available to the left of the trapezoidal group. One way to take advantage of that extra space is to break the trapezoidal group into triangular groups so that, as we shrink the side length of the square, those triangular groups are shifted to the positions shown in the left figure at <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circs68sqCompare.gif>. Those hexagonal-lattice groups are a large equilateral-triangular one, labelled B, touching A and the right side of the square; a large right-triangular one, labelled C, touching B and the top side of the square; a small equilateral-triangular one, labelled D_1, touching A and C; and a small right-triangular one, labelled X, touching D_1 and the left side of the square. The side length s_ts is then determined so that X also touches the top side of the square. (This fully describes the structure when N = 68. In general however, the structure may, as shown later, have more small equilateral-triangular groups D_i. And the group X of circles which remain after forming the last of those small equilateral-triangular groups will not necessarily be right-triangular; rather, in general, X is trapezoidal.) Side length s_ts for the triangle-shift archetype cannot, in general, be expressed in closed form, as we did for s_t&t, unless we were allowed to use "root objects" (as in some computer algebra systems). For our example with N = 68, s_ts can be determined by solving a system of five quadratic equations, dictated by the ways in which the hexagonal-lattice groups touch each other. Solving that system, we obtain s_ts = 15.994879..., a better upper bound than s_t&t for the side length s of the optimal packing. -------------------------------------------------------------------------- The triangle-shift archetype itself does not give the optimal packing in this case. For comparison, at the above link, the archetype is shown at the left and my packing for N = 68, having side length 15.994861..., is shown at the right. Note that circles in group C and some circles in group B had to be repositioned to get a better packing than the archetype. Of course, my packing might not be optimal, but at least we can say that the optimal packing's side length s <= 15.994861... Since the optimal packings in the triangle-shift family do not necessarily fit the archetype exactly, the family should be thought of as a "pattern class", as the term is used in NACPS (p. 123), meaning that the archetype provides a reasonable _approximation_ of the optimal packings in the family. But there are cases in which the archetype gives exactly the presumably optimal packing. One such case is already known, N = 247 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq247.html>, and others, N = 1817 and 4106, will be newly presented below. -------------------------------------------------------------------------- For another example, notice that, taking p = 26 and q = 15, p/q overestimates sqrt(3) We will therefore be able to pack N = ceiling((p + 1)(q + 1)/2) = 216 unit circles in a square using the triangle-shift method. But whenever q is odd, as in this example, there will be two different archetypal packings, depending on whether a unit circle is centered at the vertex of A's right angle or not: (1) The left figure at <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circs216sq.gif> shows one of those archetypal packings. Presented earlier in this thread, it is the best packing for N = 216 previously known, with s_ts = 27.999895208... Note that it has two small equilateral-triangular groups, D_1 and D_2, and that the remaining circles form a right-triangular group X which is part of the same hexagonal lattice as C. Except for circle #12, a rattler, the packing is rigid. (2) The right figure at the above link shows a new packing, with side length 27.99989448830799697857..., a modification of the other archetypal packing. For that archetype, the circles near its upper left corner would have been in a trapezoidal group X, part of the same hexagonal lattice as C. But since there would have been extra space between X and the left side of the square, the packing would not have been rigid. Adjusting circles to take advantage of that extra space, we obtain the new, improved packing. -------------------------------------------------------------------------- There is more to be said about general characteristics of this family. In particular, it will be interesting to see what happens for large N. But that will be covered in part 2. To conclude part 1, we give various packings in the family, with comments. Several of these are density record packings. And a few are noted as being suboptimal. -------------------------------------------------------------------------- -------------------------------------------------------------------------- N = 418 p = 37, q = 21, p/q - sqrt(3) = 0.02985... s = 38.913303138863028028609... suboptimal (s = 38.913316... for the archetype) 1141 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ418sq.gif> The best packing previously known has side length s = 38.91369... and 1084 contacts. The new packing is better than the archetype but is still suboptimal. Note that circle #160 is a rattler. That implies that circle #184 is also loose, and that implies that circles #183 and 202 are loose, etc... Looseness, in this case, is a contagion which spreads throughout the whole packing. I choose not to show all of the circles as rattlers simply because doing so would have obscured the triangle-shift structure. Also note that p is _odd_ here. The triangle-shift family was found by searching for packings associated with fractions p/q which overestimate sqrt(3) and have p even. But there is nothing which mandates, for this family, that p must be even. Indeed, there are many good triangle-shift packings with p odd. -------------------------------------------------------------------------- N = 492 p = 40, q = 23, p/q - sqrt(3) = 0.0070796... s = 41.99273551503355601001... 1371 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circs492sq.gif> The best packing previously known has side length s = 41.9951... and 567 contacts. -------------------------------------------------------------------------- N = 780 p = 51, q = 29, p/q - sqrt(3) = 0.026569... s = 52.8734833175458170929415... (s = 52.8757... for the archetype) 2214 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ780sq.gif> This packing is very neat. It improves on the archetype in a specific way which will be seen in two other packings below, N = 1591 and 3203. As such, it is worth describing carefully: Referring to the figure, the archetype would have had a trapezoidal hexagonal-lattice group in the upper left corner of the square. The vertices of that trapezoid would have been the centers of circles #21 and 129 and the topmost points of circles #24 and 130. But of course that would have left substantial space between the right side of the trapezoid and the left side of the large right triangle C. To take advantage of that space, we break the trapezoidal group into three pieces: 1) an equilateral-triangular group, its vertices being the centers of circles #21, 24 and 94; 2) a right-triangular group, its vertices being the centers of circles #48, 95 and 96; and 3) a columnar group, consisting of circles #129 and 130. This allows the side length of the square to be reduced, as shown. -------------------------------------------------------------------------- N = 822 p = 52, q = 30, p/q - sqrt(3) = 0.00128... s = 53.9995653581407481787552800908613... suboptimal (s = 53.9995653581407481787552800908664... for the archetype) 2330 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/subopt822sq.gif> This packing is suboptimal for the same reason that the packing given above for N = 418 is suboptimal. In this case, circle #199 is loose, implying that circle #236 can be loosened, implying that circles #235 and 261 can be loosened, etc. But even though not fully optimized, this packing is still almost certainly a density record. -------------------------------------------------------------------------- N = 1307 p = 66, q = 38, p/q - sqrt(3) = 0.00479... s = 67.9910501032779180646275... (s = 67.99105078... for the archetype) 3753 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ1307sq.gif> -------------------------------------------------------------------------- N = 1591 p = 73, q = 42, p/q - sqrt(3) = 0.00604... s = 74.9827631580596116369814... 4596 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ1591sq.gif> This neat packing is improved over the archetype in the same way as described above for N = 780. -------------------------------------------------------------------------- N = 1817 p = 78, q = 45, p/q - sqrt(3) = 0.00128... s = 79.99899806096441158999... 5268 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circs1817sq.gif> This packing is archetypal and is almost certainly a density record. -------------------------------------------------------------------------- N = 3203 p = 104, q = 60, p/q - sqrt(3) = 0.00128... s = 105.9982427170894915127586... (s = 105.99830... for the archetype) 9364 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ3203sq.gif> This neat packing is almost certainly a density record. It is improved over the archetype in the same way as described above for N = 780. -------------------------------------------------------------------------- N = 4106 p = 118, q = 68, p/q - sqrt(3) = 0.00324... s = 119.986708218048413640656... 12051 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ4106sq.gif> This packing is archetypal. -------------------------------------------------------------------------- N = 4978 p = 130, q = 75, p/q - sqrt(3) = 0.00128... s = 131.99727650071032184727630... suboptimal (s = 131.997283... for the archetype) 14607 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ4978sq.gif> This packing is suboptimal. As shown, it is rigid, except of course for the five rattlers, shown in red. But the circle at the top of the twelfth column from the left could be repositioned slightly so that it would be a rattler and then, as for N = 418, the looseness would spread... But even though not fully optimized, this packing is still almost certainly a density record. -------------------------------------------------------------------------- David W. Cantrell
From: David W. Cantrell on 2 Jul 2010 00:22 In a recent response to James Waldby, before introducing the triangle-shift family, I had said: > ...take a look at N = 418. It does fit a family which I recognize > (but haven't mentioned before) ... and N = 378 is in the same family > as N = 418. In this article, that family is introduced briefly and two improved packings are presented. -------------------------------------------------------------------------- Two examples of the family in question are N = 72 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq195.html> and N = 195 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq195.html>. A brief glance at those packings should make the pattern evident. Like triangle-shift packings, packings in the new family have two large right-triangular hexagonal-lattice groups of unit circles and a large equilateral-triangular group. The other circles are grouped in columns, rather than in the smaller equilateral-triangular groups found in triangle-shift packings. Other known members of the family include N = 90, 110, 132 and 224. Curiously, the new family competes for more-or-less the same niche as the column-shift and triangle-shift families when p is odd. At the time I responded to James, the best packing known for N = 418 was indeed in the new family, but that was soon bettered by a triangle-shift packing. -------------------------------------------------------------------------- N = 378 s = 36.9647264079734566272461... 1017 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ378sq.gif> The best packing previously known had s = 36.9653... and 983 contacts. That packing didn't quite fit the archetype for the family; the new packing does. -------------------------------------------------------------------------- N = 672 s = 48.9835873486371916431324... 1836 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ672sq.gif> The best packing previously known had s = 48.9853... and 833 contacts. (And prior to that, the best packing known was a column-shift packing, having s = 48.9857...) -------------------------------------------------------------------------- David W. Cantrell
From: David W. Cantrell on 7 Jul 2010 20:07 Some triangle-shift packings as well as some packings obtained by appending one or two columns to a triangle-shift packing are presented, with comments. -------------------------------------------------------------------------- N = 279 (triangle-shift) s = 31.9300827952756442948399... suboptimal 748 contacts shown at the left of <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ279sq.gif> The best packing previously known had s = 31.9316... and 573 contacts. -------------------------------------------------------------------------- N = 280 (triangle-shift + col.) s = 31.9789154528744276481019... suboptimal 752 contacts shown at the right of <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ279sq.gif> The best packing previously known had s = 31.9812... and 223 contacts. -------------------------------------------------------------------------- The packings for N = 279 and 280 were shown together at the above link for the sake of comparison. It is not at all uncommon to have such a pair of packings, in which the first is a fairly dense triangle-shift packing and the second is formed by appending a column to a rhombic or triangle-shift packing. But it is not so common to have a third packing in the group: N = 281 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq281.html> is a grid packing with three columns appended. At least two more triplets of such packings are known. One of them is (85, 86, 87), shown at <http://hydra.nat.uni-magdeburg.de/packing/csq/d8.html>. The packing for N = 85 is triangle-shift; the packing for N = 86 has an added column, albeit inserted in the middle, rather than at a side, of the packing; and the packing for N = 87 has three columns appended to a grid packing. Another triplet is (585, 586, 587), the first two packings of which are new, shown at <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ585sq.gif>, and the last is shown at <http://hydra.nat.uni-magdeburg.de/packing/csq/csq587.html>. Not surprisingly, of course, pairs of such packings are more frequent than triplets. One of the earliest such pairs, shown at <http://hydra.nat.uni-magdeburg.de/packing/csq/d6.html>, is N = 68 (triangle-shift) and N = 69 (grid + 2 cols.) Another pair is (247, 248) at <http://hydra.nat.uni-magdeburg.de/packing/csq/d21.html>. Many other pairs can already be found at Packomania, and several others, including (538, 539), (880, 881) and (941, 942), will be submitted soon. -------------------------------------------------------------------------- N = 315 (triangle-shift + 2 cols.) s = 33.9773612511606594854421... 810 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ315sq.gif> The best packing previously known had s = 33.9881... and 477 contacts. (In the new packing, there are several circles which, although not touching, are very close together. Since Packomania uses only 30 significant digits, it is likely that, when the new packing appears there, the reported number of contacts will exceed 810.) -------------------------------------------------------------------------- N = 896 (archetypal triangle-shift) s = 56.6893643561340760085219... 2557 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/ts/circ896sq.gif> The best packing previously known had s = 56.6991... and 516 contacts. -------------------------------------------------------------------------- As noted in my initial posting about the triangle-shift family, such packings are often difficult to optimize. Due to that difficulty, many of my new packings (such as N = 279 and 280) have not been fully optimized and the packings are not rigid. And when optimization is attempted, as for N = 315 above, the resulting packing can be very messy (and may still not be optimal). But in some cases, the packings are at least local optima. For example, N = 896 is archetypal. And N = 585 and 586, although not archetypal, are very neat. -------------------------------------------------------------------------- "The Triangle-Shift Family, Part 2", which will discuss behavior for large N, is still being prepared. David W. Cantrell
From: David W. Cantrell on 11 Jul 2010 17:56
Earlier in this thread, there was a brief detour in which packings of unit circles in rectangles with length/width = 5 or 10 were considered. (The first of the three posts in that detour is <http://groups.google.com/group/sci.math/msg/df25a12618e2183d>.) Recently at Packomania, Eckard Specht has added packings of circles in rectangles with length/width = 10/3: <http://hydra.nat.uni-magdeburg.de/packing/crc_300/crc.html>. In this post, some improved packings of that type are given, together with comments, including reasons why packings in (non-square) rectangles are or are not interesting. ------------------------------------------------------------------------ Note: Packing _unit_ circles in the smallest possible rectangle with length/width = 10/3, the smaller dimension, width, of that rectangle equals the quantity now called "ratio" at Packomania. ------------------------------------------------------------------------ Several of my packings are only slight improvements of ones now shown at Packomania. I will not be posting figures for some of the improved packings, supposing that they will appear at Packomania in due course. (Below, "new" and"old" give, resp., the number of contacts in my packing and in the one currently shown at Packomania.) N width new old contacts 31 6.219249170995002809467646... 63 53 43 7.106245261194258251113958... 101 95 47 7.375672753530237878952092... 95 78 49 7.605448432271752180308248... 90 82 --------------------------------------------------------------------------- Figures for improved packings for N = 46 and 50 are shown together at <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/4650in10x3.gif>. Their widths are 7.199994466957570160112695... and 7.702329400757996835427410..., resp. The new packings are significant improvements. For N = 46, the old packing had 35 contacts, while the new has 115. For N = 50, the old packing had 104 contacts, while the new has 124. By the way, we can sometimes give precise values in terms of radicals. For example, for N = 50, the width is exactly 3/65 (62 + 45 sqrt(3) + 2 sqrt(420 sqrt(3) - 546)) --------------------------------------------------------------------------- N = 200 width = 14.99757249125798345467314... 536 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs200rect10x3.gif> The best packing previously known had width = 15.0160... and 503 contacts. Note that the new packing happens to reduce the width to slightly less than 15. So if someone asks how many unit circles can be packed in a 50x15 rectangle, the answer is "At least 200." --------------------------------------------------------------------------- General comments about packing unit circles in rectangles It's interesting to compare packings in squares to packings in other rectangles. Not surprisingly, one finds the same classic "modes" of packing in both squares and other rectangles. For example, a glance at <http://hydra.nat.uni-magdeburg.de/packing/crc_300/d3.html> will reveal that the packings for N = 23, 24 and 26 are grid packings, while those for N = 27 and 30 are row-shift packings (that is, a column-shift turned sideways). But the packings for N = 46, 50 and 200 are of an even more common type in which there are equilateral-triangular hexagonal-lattice groups of circles. (These look a good bit like the upper left corner of triangle-shift packings in squares.) As length/width increases, that type of packing seems to become more dominant. And for packings of that type, the messiness tends to be confined to the ends -- often just one end -- of the rectangle. The packing shown above for N = 200 is a good example of that phenomenon. Due to the dominance of that type of packing and the fact that the messy part is then often just at the ends of the rectangle, packings in non-square rectangles tend to show less variety and to be easier than packings in squares. For that reason, packing in squares is more interesting to me. (Of course, I'm not saying that there are no messy cases when the rectangle is not a square. The packing for N = 70 circles in a 5x1 rectangle <http://hydra.nat.uni-magdeburg.de/packing/crc_200/crc70_0.200000000000.html> comes to mind...) David W. Cantrell |