Prev: Delayed differential equation
Next: Ordered computation of eigenvalues from good initial estimates, without explicit sorting
From: David W. Cantrell on 23 Jul 2010 16:48
The rhombic family of packings of unit circles in squares may be
generalized to obtain a new family: the parallelogramic family.
It contains some new packings which are almost certainly density
records, five of which are presented.

--------------------------------------------------------------------------

Grid packings were generalized to rhombic packings earlier in this thread.
But there are other, closely related packings which are not quite as
"regular" as rhombic packings. In the new family, unit circles are again
found in hexagonal-lattice groups. But those groups are not necessarily
rhombic; they can, more generally, be parallelogramic. Looking at some
already known packings of this type should make their structure clear:
N = 63 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq63.html>
N = 114 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq114.html>
N = 270 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq270.html>

It happens that none of those three examples are density record packings.
(A packing of N circles is a density record if the packing's density is
greater than that for any lesser number of circles.) But some
parallelogramic packings are almost certainly density records. Five such
packings are now given.

--------------------------------------------------------------------------

N = 572
s = (1934 + 2527*Sqrt[3] + 209*Sqrt[191 + 168*Sqrt[3]])/241
= 45.2253483317...
1311 contacts
symmetry group C_2
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs572sq.gif>

The best packing previously known had
s = 45.2253483323... and 663 contacts.

--------------------------------------------------------------------------

N = 765
s = (4715 + 6498*Sqrt[3] + 209*Sqrt[-5 + 1116*Sqrt[3]])/482
= 52.1717261201702...
1813 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs765sq.gif>

The best packing previously known had
s = 52.171733... and 673 contacts.

--------------------------------------------------------------------------

N = 1435
s = (7014 + 10469*Sqrt[3] + 209*Sqrt[5*(-619 + 580*Sqrt[3])])/482
= 71.2109...
3603 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs1435sq.gif>

The best packing previously known was a grid packing with
s = 71.2112... and 2871 contacts.

--------------------------------------------------------------------------

N = 3520
s = (3*(16222 + 24975*Sqrt[3] + 390*Sqrt[2601 + 4736*Sqrt[3]]))/2701
= 111.089354...
8235 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs3520sq.gif>

The best packing previously known was a grid packing with
s = 111.089363... and 7041 contacts.

--------------------------------------------------------------------------

N = 4838
s = (10*(6151 + 9720*Sqrt[3] + 117*Sqrt[-2997 + 7968*Sqrt[3]]))/2701
= 130.128734...
11681 contacts
symmetry group D_1
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs4838sq.gif>

The best packing previously known was a grid packing with
s = 130.128755... and 9678 contacts.

--------------------------------------------------------------------------

More parallelogramic packings will probably be posted later.

David W. Cantrell
From: David W. Cantrell on 5 Aug 2010 19:39
Archetypal parallelogramic packings can often be improved by modifying the
packing near a corner of the square. This leads, for example, to a packing
for N = 572 which is even better than the one posted previously. Other
examples are given. Particularly noteworthy is a packing for N = 1166,
which is almost certainly a density record.

--------------------------------------------------------------------------

David W. Cantrell <DWCantrell(a)sigmaxi.net> wrote:
> The rhombic family of packings of unit circles in squares may be
> generalized to obtain a new family: the parallelogramic family.
> It contains some new packings which are almost certainly density
> records, five of which are presented.
>
> -------------------------------------------------------------------------
>
> Grid packings were generalized to rhombic packings earlier in this
> thread. But there are other, closely related packings which are not quite
> as "regular" as rhombic packings. In the new family, unit circles are
> again found in hexagonal-lattice groups. But those groups are not
> necessarily rhombic; they can, more generally, be parallelogramic.
> Looking at some already known packings of this type should make their
> structure clear:
> N = 63 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq63.html>
> N = 114 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq114.html>
> N = 270 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq270.html>
>
> It happens that none of those three examples are density record packings.
> (A packing of N circles is a density record if the packing's density is
> greater than that for any lesser number of circles.) But some
> parallelogramic packings are almost certainly density records. Five such
> packings are now given.
>
> -------------------------------------------------------------------------
>
> N = 572
> s = (1934 + 2527*Sqrt[3] + 209*Sqrt[191 + 168*Sqrt[3]])/241
> = 45.2253483317...
> 1311 contacts
> symmetry group C_2
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs572sq.gif>
>
> The best packing previously known had
> s = 45.2253483323... and 663 contacts.
>
> -------------------------------------------------------------------------

An even better packing for N = 572, having
s = 45.225318524066822595891... and 1514 contacts, is shown at
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/bettr572sq.gif>.

The new packing, unlike the previous one, is not archetypal. Although It
does largely consist of parallelogramic hexagonal-lattice groups of circles
(or portions of such groups, produced by truncations at sides of the
square), this regularity breaks down in a corridor leading into the lower
left corner of the square. (And due to this breakdown of regularity, the
side length s cannot be given neatly, in terms of radicals, as can be done
for archetypal parallelogramic packings.)

The parallelogramic family is now seen to be like the triangle-shift family
in the sense that, in both families, many optimal packings are not
archetypal, requiring some breakdown in regularity in order to achieve
optimality. Both families may be considered as "structure classes", rather
than "pattern classes", so that their archetypes provide at least fair
approximations of optimal packings. (For example, the archetypal packing
which was modified to give the new packing for N = 572 had s = 45.225320...)

Another packing in the family which is not archetypal and also almost
certainly a density record is

-------------------------------------------------------------------------

N = 1166
s = 64.264381294241885680772...
3196 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs1166sq.gif>
Regularity breaks down in a corridor leading to the lower right corner.

The best packing previously known had
s = 64.26447... and 121 contacts.

-------------------------------------------------------------------------

Some optimal packings are, presumably, given by archetypal members of the
parallelogramic family. Two of these are given below.

-------------------------------------------------------------------------

N = 368 archetypal
s = (12*(122 + 156*Sqrt[3] + 7*Sqrt[-219 + 572*Sqrt[3]]))/193
= 36.47630...
879 contacts
symmetry group D_1
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs368sq.gif>

The best packing previously known had
s = 36.47646... and 894 contacts.

--------------------------------------------------------------------------

N = 525 archetypal
s = (1807 + 2448*Sqrt[3] + 84*Sqrt[-936 + 986*Sqrt[3]])/193
= 43.42327...
1300 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs525sq.gif>

The best packing previously known had
s = 43.42368... and 340 contacts.

-------------------------------------------------------------------------

David W. Cantrell
First  |  Prev  | 
Pages: 1 2 3 4 5 6 7
Prev: Delayed differential equation
Next: Ordered computation of eigenvalues from good initial estimates, without explicit sorting