Back to the House of Dave

 

NOTICE - If you have this page linked or bookmarked, please refer to the page off of my spankin' new domain name

http://www.daveboll.com/packing.html - I have that URL forwarded here, but if I need to move my site again,

you'll never have to change it.

 

Optimal Packing Of Circles And Spheres

 

10/2/00 - a link to the packing paper I co-wrote with Jerry Donovan, Boris Lubachevsky, and Ron Graham - click on Current Volume, and look for R46

Added links to Jerry Donovan's packing page, which contains a better-than-mine program for packing.

 

I got interested in packing circles through one of Martin Gardner's columns, in which he discusses the problem of packing 10 identical circles in the smallest possible square. I thought about it for a while, and thought of an algorithm that could be used to find good packings for circles in squares, circles in larger circles, spheres in cubes, and separating points on the surface of a sphere.

Gardner's article detailed the history of the 10 circle problem, which has had four separate journal articles (by different authors), each of which reported a packing result for 10 circles in a square that was superior to the one before it.

Here's the general algorithm I use (illustrated for packing circles in a square)

The above algorithm generates good, locally minimal solutions; and if it is run for several million iterations, it will find a very good solution. It is also easily extendable to packing circles in any easily defined shape (rectangles, hexagons, larger circles, etc), and can be easily extended to packing spheres as well, and to moving points around on the surface of a sphere. It even has easy higher-dimensional implementations. Finally, it is much less complicated than the "coulomb force repulsion" algorithms I have seen elsewhere. Although, these may lead to slightly different packs: my program tries to maximize the minimum distance between points, and there are several other ways to define a minimal pack (minimize the potential, minimize some other power-law distance metric, etc).

FWIW, my program also found the best known solution for the 10 circle problem. It's cranked away on it for literally weeks, and I suspect that one is really the best. For "small" N (say, under 16 or so), the optimal solutions are found quite quickly; for example, I get the best 10 circle solution inside of 5 minutes.

Best results: I used to have some pics of circle-in-square packs here that were better than any I had seen, but I have since found out that it was because I hadn't seen them all! Here is a link to a page that shows pics of the packs thru N=25. Mine are equivalent to this list, give or take some rounding errors.

Recently a co-worker of mine, Jerry Donovan, wrote a slightly different program to pack circles in a square. We're still not sure what the important differences are, but his results are consistently better than mine. We're hoping to extend his algorithm to the other 4 cases (circles in circles, points on the surface of a sphere, spheres in spheres, spheres in cubes). The table has been updated below to reflect his best results from N=26 to N=48. His algorithm (unlike mine) finds the best packs for N=25 and N=36, and converges in just a few iterations to values that takes mine thousands of iterations.

For smaller values of N for which good packs are known, the new algorithm converges rapidly - within just a few iterations - to the best known solutions. This increases our confidence that the values of N for which we have not seen a published solution are also packed well, and may represent new minimal packings. So far, the circle-in-circle and circle-in-square results have been updated with the results from the new algorithm.

Packing a square number of objects in a square

Another very interesting question is, when does a square lattice packing become inefficient? Packing N^2 circles in a square can always be done by doing a square packing. For N=2,3, this is provably the best way to do it. But, where does it break down? Well, on my top-level home page is a bitmap of my best N=8 (64 circles) packing, fitting in a square slightly smaller than a square packing would allow. And, here are 2 of the 7x7 (49 circle) packings I have that are better than a square lattice packing. From left, the radii are .07144+, .0715+, and .07143+ (the square lattice pack has a radius of 1/14, or .0714285)

The top row of the left-hand pack may make it look like it's not better than a square lattice, but if you look at the actual point positions, you can see that #'s 2, 4, and 6 from left are shifted down ever so slightly, and #'s 1, 3, 5, and 7 are flush against the top edge. The one on the right is my worst-so-far pack that is still better than a square lattice pack.

So, the break point is N=4,5,6. I really don't have additional data, except that my programs have tried to find solutions for N=6 for a very long time (I use it as a screensaver) without finding anything. I think that N=4 (16 circles) and N=5 (25 circles) are most efficiently done as a square pack. My algorithm does not find square lattice packs easily, it seems to "prefer" some kind of hexagonal pack, which is actually a good thing. My best current guess is that although 49 circles can be packed better than a 7x7 square lattice, 36 circles cannot be packed better than a 6x6 square.

We are going to unleash Jerry's new algorithm on N=36 soon. Failure to find a packing superior to a 6x6 square lattice would support the notion that 49 is the smallest square number that can be packed tighter than a square lattice pack allows.

Here's a vague hand-waving argument why: 7 is the smallest integer for which (n+1)cos30 < n. And, cos30 represents the space-saving fraction of a hexagonal pack (in 1 dimension) as opposed to a square lattice pack. In other words, although a hexagonal pack is clearly superior to a square lattice pack, squares smaller than 7x7 don't have the room to take advantage of it.

I don't have different N-values leading to packs with the same metrics among the new circle-in-square data.

Separating points on the surface of a sphere

I recently (12/23/96) began getting some better results for separating points on the surface of a sphere. One surprising-to-me result is that for N=20, I can do significantly better than the metric for the verticies of a dodecahedron. But, then again, for N=8 you can do better than a cube, so maybe it's not such a shock.

The pics above are 2 of my better packs, for N=18 (right) and N=23 (left) points. Thanks to Martin Trump for ideas on how to write a program to produce pictures like the above.

I have no duplicate packing metrics for different N values among the points-on-a-sphere data, although there are several pairs in the table below that are extremely close.

Packing spheres in spheres.

Here's a shot of my best N=30, 17, and 32 packs, the spheres are color coded for depth. All 3 of these packs are quite good - I know that, because I've found them recently. I've been running packing programs nightly for a long time now, so on the rare occasion I find a new one, I know it's pretty decent.

Again, we have different N-values leading to the same size packs. My best for N={26,27} are the same, as are N={28,29}. I'll have to let my program crunch on 26-29 over a weekend or long holiday sometime. <--- Update, did that, and now I have no duplicate packs among the sphere-in-sphere data.

Packing spheres in cubes

There's a couple of interesting questions here:

1) What is the analagous circles-in-squares number for the smallest cube for which it is possible to do better than a cubic lattice pack? My intuition says either 5 or 6, and it would be interesting to replicate my circle-in-square argument here to get a guess, but I'll have to figure out how to find the angle. It's not 45, is it? If so, N=5 should work.

2) Again, duplicate packs. I'll make a picture of the 16 and 17 packs (which are currently close to the same). 28-32 are very close (btw, 32 is the first pack that exceeds the density of a cubic lattice pack), as are 45-48.

Packing circles, pics

I used to have pictures here, but all my results have improved drastically in the last couple weeks, so I'll have to generate some new pictures.

Graphing packing density as a function of N shows some interesting features:

The minimum packs - the local minima in the above graph - start out 1,7,19,37,61,91... an obvious series. The packs are pretty sensible as well: each sucessive one places a new ring of circles around the previous packing in the series. But, N=55,85 are also local minima, and they're different animals, they are hexagonal close-packs with some extras thrown in around the edges.

Here's a pic of N=55 compared with 61, you'll see what I mean:

 

N=85 is the next step up from N=55, the central hex is larger by one on all sides, and there are 4 extra circles between each edge and the circle, rather than 3 for N=55. It is clear that packs like this will eventually dominate, according to the density graph above, N=91 (the highest concentric-circle pack shown) is already not terribly superior to its peers.

Packing Non-Circles

Packing non-circles is way, way harder than packing circles. Eric's packing site has some nice pictures of good triangular and square packs. I'm not aware of any program that will find them, but if I ever get the mojo, here is how I'll write it:

Loop:

1) Separate the centers of the non-circles by taking one 'step' of my circle-packing algorithm described above.

2) Hold the centers in place, and adjust the rotation angle of each non-circle. This could be done in a similar way by seeing if an adjustment of theta (in either direction) increases the distance from the corner points to their neighbors. Let the algorithm run until it gets stuck, then decrease theta.

Here's my best results to date, for the following cases:

In all cases, I use the following for the container shape:

In the first three cases, the numbers given are the radius of my current best packing element. For separating points on the surface of a sphere, the number given is the minimum angle between 2 points (vertex at the center of the sphere), in degrees. For packing spheres in cubes, it is the radius of my best packing sphere. If you are interested in seeing actual point positions for any of these packs, just send me some email and I'll send them to you.

Things To Pack Circles in Squares Circles in Circles Spheres in Spheres Points on a Sphere Spheres in Cubes
 14  .129332  .231031  0.323313 55.670  
15 .127330 .221173 0.318305 53.638 .192293
16 .125 .216665 0.310976 52.206 .188688
17 .117197 .208667 0.305694 51.073 .188618
18 .115521 .205605 0.301296 49.547 .187644
19 .112265 .205605 .295332 47.651 .183194
20 .111382 .195224 .287851 47.421 .178402
21 .106860 .190392 .286833 45.585 .177112
22 .105665 .183833 .279334 44.701 .173159
23 .102802 .180336 .275081 43.698 .171190
24 .101382 .176939 .271336 43.682 .170493
25 .1 .173702 .271120 41.550 .167731
26 .096362 .171580 .2666792 40.996 .166727
27 .095420 .169307 .262120 40.586 .166667
28 .093672 .166253 .260096 39.192 .160182
29 .092463 .162904 .257819 38.596 .160184
30 .091671 .161349 .254780 38.414 .160184
31 .089331 .158945 .253115 37.628 .160176
32 .087858 .155531 .250712 37.334 .160144
33 .087230 .154160 .248703 36.030 .154344
34 .085270 .151264 .247006 35.560 .151950
35 .084291 .149294 .244773 35.110 .150250
36 .083333 .148207 .241787 34.888 .149212
37 .082090 .147956 .240441 34.204 .148885
38 .081709 .143639 .240360 34.052 .148865
39 .081367 .141644 .236703 33.294 .147599
40 .079187 .140374 .234871 32.958 .146404
41 .078450 .137738 .232702 32.544 .144743
42 .077801 .136113 .232119 32.109 .142797
 43  .076321  .134684  .229667  31.844  .141464
 44  .075782  .133307  .228083  31.793  .140596
 45  .074727  .132031  .226594  31.007  .139942
 46  .074272  .130716  .225164  30.641  .139844
 47  .073112  .129451  .223342  30.389  .139827
 48  .072432  .128345  .222363  30.106  .139817
 49  .071693  .126793  ,220980  29.700  .136206

 

Here's the executable programs that generate the packings. They run under Win3.1, Win95, and WinNT, although you may need to disable your screen saver to run them - I use a blank screen as a screensaver, and it seems to work OK. Grab these programs, and put them anywhere on your hard disk. They all require a 2-line data file, named {square.dat, circle.dat, etc.}. You'll have to create this yourself, it's just 2 numbers:

1) # of things to pack

2) Number of times to try packing it

For example, if you wanted to check out square.exe (which packs circles in a square) with N=26, your file would look like this:

26

999999

I usually set the 2nd number to some big value, and then manually kill the program when I'm done. The program will create a file {square.out, circle.out, etc}, which contains listings of sucessively better packs. The final one will always be the best.

If you generate a pack using these programs that is better than one you see on the table, email it to me at dj1@frii.com and I'll update my table.

Program for packing circles in squares: square1.exe

Program for packing circles in circles: circle1.exe

Program for packing spheres in spheres: sphere.exe

Program for packing points on the surface of a sphere: sphersrf.exe

Jerry's packing site with a far better program (complete with visual output) that does everything but points on the surface of a sphere.