Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University 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.uni-magdeburg.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.uni-magdeburg.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.uni-magdeburg.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
|
|
|
|
