Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Packing unit disks in rectangles
Posted:
Oct 1, 2012 12:04 AM


Find the rectangles in which N unit disks may be packed as densely as possible.
Packomania now has a page devoted to the above problem: <http://hydra.nat.unimagdeburg.de/packing/crc_var/crc.html>. And Eckard Specht has recently published "High density packings of equal circles in rectangles with variable aspect ratio" <http://www.sciencedirect.com/science/article/pii/S0305054812001141>.
For the great majority of N, these packings are rather boring, having the disks simply in a hexagonal lattice, such as for N = 81: <http://hydra.nat.unimagdeburg.de/packing/crc_var/crc81_0.516346035226.html>. But there are more interesting packings for some N.
Consider the packing for N = 37: <http://hydra.nat.unimagdeburg.de/packing/crc_var/crc37_0.211285615587.html>. It can be obtained by starting with a hexagonal lattice packing for N = 38, removing one disk at an end of the middle row, and then adjusting the remaining disks at that end of the rectangle in order to maximize the density of the packing. Specht calls this procedure closing a monovacancy. Up to N = 500, all optimal packings which can be obtained in this way have already been found.
We now consider four new cases in which more than one disk must be removed from a hexagonal lattice packing before we may adjust the remaining disks in order to maximize density.

Case 1: N = 169, 321 and 393
A new packing for N = 169 is shown at <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/crc169.gif>. All contacts are as they appear to be, except that disk 1 does not touch the right side of the rectangle and that disks 3 and 4 do not touch disk 2. This new packing has density 0.8637304121097650539640552982795... The best packing previously known has density 0.86357...
The new packings for N = 321 and 393 can be obtained from the packing for N = 169 merely by extending its hexagonal lattice to the left, as well as adding one row of disks above and one row below.

Case 2: N = 381 and 453
A new packing for N = 381 is shown at <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/crc381.gif>. All contacts are as they appear to be, except that disks 1 and 2 do not touch and that disk 3 is a rattler (i.e., has no contacts). This new packing has density 0.878483083904656665820226209883... The best packing previously known has density 0.87822...
The new packing for N = 453 can be obtained from the packing for N = 381 merely by extending its hexagonal lattice to the left.

Case 3: N = 411 and 433
A new packing for N = 411 is shown at <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/crc411.gif>. All contacts are as they appear to be. (And there is one obvious rattler.) This new packing has density 411 pi/((1 + 5 sqrt(3))(148 + sqrt(3) + sqrt(520 sqrt(3)  117)/13)) = 0.880008... The best packing previously known has density 0.8793...
The new packing for N = 433 can be obtained from the packing for N = 411 merely by extending its hexagonal lattice to the left.

Case 4: N = 421
A new packing for N = 421 is shown at <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/crc421.gif>. All contacts are as they appear to be, except that disk 1 is a rattler. (And there is another rattler, but it is obvious.) This new packing has density 0.879785792237024456710589954712... The best packing previously known has density 0.87952...

David W. Cantrell



