-- Packing unit circles in squares: new results
David W. Cantrell
problem. This thread will present a few improvements, made by "tightening"
previously known packings.
For previously known packings, see the appropriate section of Eckard
Specht's excellent Packomania:
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html>.
(Note that, once he has shown my new packings at his site, the links given
below may become invalid.) In my figures, tangencies are indicated by a
small normal segment, and circles are color-coded according to their number
of tangencies: red, 0; purple, 3; green, 4; yellow, 5; orange, 6.
When comparing my packings with those shown at Packomania, it is easiest to
compare densities. I denote density by p (for rho). Densities given at
Packomania have only 12 significant digits. This is unfortunate because
some of my improvements are so slight that 12 digits are insufficient to
distinguish my denser packing from the best packing previously known. (See
N = 67 for an example.)
For each of my packings, I also state the inradius r (i.e., half of the
side length) of the enclosing square. [Note that, at Packomania, "radius"
is different, being the radius of N circles packed in a unit square.]
------------------------------------
N = 66
r = 7.95389832678370009619190233833517791609612361...
p = 0.81935809082853758087771085403826179585948676...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs66sq.gif>
The best packing previously known has density p = 0.819358090747.
------------------------------------
N = 67
r = 7.988824651488013966865690051652444494170052070638613133440977329032915...
p = 0.824515655813954973091621625909246965450782032326726697260687946138327...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs67sq.gif>
The best packing previously known has density p = 0.824515655814, the
last digit of which was presumably rounded up.
The case for N = 67 provides an excellent example to show just how
slight some of my improvements are. If you look at either my packing
or at the one shown at Packomania, you will see a large group of
circles, several of which touch the right side of the square, which
are precisely in a hexagonal lattice. That group of unit circles in my
packing is _slightly_ closer to the bottom side of the square than
the similar group is in the best packing previously known. How much
closer? Only about 9 * 10^-45.
------------------------------------
N = 68
r = 7.99743084159707382673613400757502754596314060...
p = 0.83502178830167649807538601106800978977863397...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs68sq.gif>
The best packing previously known has density p = 0.835021788293.
------------------------------------
N = 84
r = 8.95148308706834507357099876376304757429943342539669758588299251599...
p = 0.82333992692510077974748869010834664113579634306042877994739284602...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs84sq.gif>
The best packing previously known has the same density as mine to 12
decimal places.
------------------------------------
N = 85
r = 8.9798557425792022476805302926495736012040593137003...
p = 0.8278851395672735231029826347399750193631606379732...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs85sq.gif>
The best packing previously known has the same density as mine to 12
decimal places.
------------------------------------
N = 86
r = 8.997174982279363207650694168748281706273880933206999800...
p = 0.834403272414697727894929633779203534633385698632393505...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs86sq.gif>
The best packing previously known has density p = 0.834403272276.
------------------------------------
N = 87
r = 9.1415600282948896055419169549415260364164735059510787963984770833...
p = 0.8176519995811763240445282228845729524649938658137756724433479863...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs87sq.gif>
The best packing previously known has the same density as mine to 12
decimal places.
------------------------------------
N = 100
r = 9.7274236263921432917145912263616910451665439831673...
p = 0.8300308266359128217408023324454546201530891073305...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs100sq.gif>
The best packing previously known has density p = 0.830030826636, the last
digit of which was presumably rounded up.
------------------------------------
On request, more significant digits (for the inradius or the density) can
be supplied easily for any of the packings above.
David W. Cantrell
achille
>
> The best packing previously known has density p = 0.830030826636, the last
> digit of which was presumably rounded up.
>
> ------------------------------------
>
> On request, more significant digits (for the inradius or the density) can
> be supplied easily for any of the packings above.
>
> David W. Cantrell
I'm confused. In the n=87 case, why the circles 52 and 60 are
both touching the edge? Is there some tiny gaps between the
circles on that column? Otherwise, I don't understand why
the circle 69 not touching the top.
David W. Cantrell
> On Feb 28, 5:23=A0pm, David W. Cantrell <DWCantr...@sigmaxi.net> wrote:
> > ------------------------------------
> >
> > N = 87
> > r =
> > 9.1415600282948896055419169549415260364164735059510787963984770833...
> > p =
> > 0.8176519995811763240445282228845729524649938658137756724433479863...
> >
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs87sq.gif>
> >
> > The best packing previously known has the same density as mine to 12
> > decimal places.
> >
> > ------------------------------------
> I'm confused. In the n=87 case, why the circles 52 and 60 are
> both touching the edge? Is there some tiny gaps between the
> circles on that column?
Yes, and the gaps aren't really tiny. You can tell that there are gaps by
noting that my figure does _not_ indicate that the circles in that column
touch.
David
achille
David W. Cantrell
> Packing N unit circles in the smallest possible square is a classic
> packing problem. This thread will present a few improvements, made
> by "tightening" previously known packings.
This post presents two more improvements, for N = 78 and 79, and
gives conjectured bounds for r in terms of N.
> For previously known packings, see the appropriate section of Eckard
> Specht's excellent Packomania:
> <http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html>.
> (Note that, once he has shown my new packings at his site, the links
> given below may become invalid.) In my figures, tangencies are indicated
> by a small normal segment, and circles are color-coded according to their
> number of tangencies: red, 0; purple, 3; green, 4; yellow, 5; orange, 6.
>
> When comparing my packings with those shown at Packomania, it is easiest
> to compare densities. I denote density by p (for rho). Densities given at
> Packomania have only 12 significant digits. This is unfortunate because
> some of my improvements are so slight that 12 digits are insufficient to
> distinguish my denser packing from the best packing previously known.
> (See N = 67 for an example.)
>
> For each of my packings, I also state the inradius r (i.e., half of the
> side length) of the enclosing square. [Note that, at Packomania, "radius"
> is different, being the radius of N circles packed in a unit square.]
>
> ------------------------------------
>
> N = 66
> r = 7.95389832678370009619190233833517791609612361...
> p = 0.81935809082853758087771085403826179585948676...
>
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs66sq.gif>
>
> The best packing previously known has density p = 0.819358090747.
>
> ------------------------------------
>
> N = 67
> r = 7.9888246514880139668656900516524444941700520706386131334409773290...
> p = 0.8245156558139549730916216259092469654507820323267266972606879461...
>
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs67sq.gif>
>
> The best packing previously known has density p = 0.824515655814, the
> last digit of which was presumably rounded up.
>
> The case for N = 67 provides an excellent example to show just how
> slight some of my improvements are. If you look at either my packing
> or at the one shown at Packomania, you will see a large group of
> circles, several of which touch the right side of the square, which
> are precisely in a hexagonal lattice. That group of unit circles in my
> packing is _slightly_ closer to the bottom side of the square than
> the similar group is in the best packing previously known. How much
> closer? Only about 9 * 10^-45.
>
> ------------------------------------
>
> N = 68
> r = 7.99743084159707382673613400757502754596314060...
> p = 0.83502178830167649807538601106800978977863397...
>
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs68sq.gif>
>
> The best packing previously known has density p = 0.835021788293.
>
> ------------------------------------
N = 78
r = 8.66513931971894778656334075069...
p = 0.815893333309535399379288603288...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs78sq.gif>
The best packing previously known has density p = 0.815893333300.
------------------------------------
N = 79
r = 8.69436725300676561082028951967...
p = 0.820806922795721980813682909691...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs79sq.gif>
The best packing previously known has density p = 0.820806922795.
------------------------------------
[Previously given improvements for N = 84-87 and 100 were snipped.]
> On request, more significant digits (for the inradius or the density) can
> be supplied easily for any of the packings above.
Conjectured upper and lower bounds for r in terms of N follow from two
conjectured inequalitites.
We conjecture that, except for N = 4 and 9,
(*) (2 r - 1)(r -1)/sqrt(3) + r >= N
with equality only when N = 1.
This leads to a conjectured lower bound for r:
For all N other than 4 and 9,
(LB) r >= (3 - sqrt(3) + sqrt(2 sqrt(3) (4 N - 3) + 4)))/4
And we conjecture that, for all N,
(**) 2/sqrt(3) r (r - (1 + 1/sqrt(2))) + 4/(4 + sqrt(2)) (r + 1) <= N
with equality only when N = 2.
This leads to a conjectured upper bound for r:
(UB) r <= (c1 + sqrt(4 sqrt(3) N (9 + 4 sqrt(2)) + c2))/(2 (4 + sqrt(2)))
where constants c1 = 5 + 3 sqrt(2) - 2 sqrt(3) and
c2 = 55 + 30 sqrt(2) - 52 sqrt(3) - 20 sqrt(6).
It is highly likely that (*) and (LB) are correct. [Indeed, I would not be
surprised if a proof could be given. Furthermore, I have little doubt that
a tighter lower bound could be given.] By contrast, (**) and (UB) seem not
as likely to be correct. They fail for four packings currently shown at
Packomania -- spec., for N = 251, 253, 257 and 258 -- but I suspect that
eventually packings satisfying (**) and (UB) will be found for those values
of N.
David W. Cantrell
David W. Cantrell
> David W. Cantrell <DWCan...@sigmaxi.net> wrote:
> > Packing N unit circles in the smallest possible square is a classic
> > packing problem. This thread will present a few improvements, made
> > by "tightening" previously known packings.
>
> This post presents two more improvements, for N = 78 and 79, and
> gives conjectured bounds for r in terms of N.
This post presents, below, an improved packing for N = 92.
This will perhaps be my last post in this thread. But note that there are
still improvements to be made for some other N < 100. (In particular, it
seems obvious that the current packings for N = 91, 93 and 98 are not quite
optimal.)
> > For previously known packings, see the appropriate section of Eckard
> > Specht's excellent Packomania:
> > <http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html>.
> > (Note that, once he has shown my new packings at his site, the links
> > given below may become invalid.) In my figures, tangencies are
> > indicated by a small normal segment, and circles are color-coded
> > according to their number of tangencies: red, 0; purple, 3; green, 4;
> > yellow, 5; orange, 6.
> >
> > When comparing my packings with those shown at Packomania, it is
> > easiest to compare densities. I denote density by p (for rho).
> >
> > For each of my packings, I also state the inradius r (i.e., half of the
> > side length) of the enclosing square. [Note that, at Packomania,
> > "radius" is different, being the radius of N circles packed in a unit
> > square.]
------------------------------------
N = 92, symmetry group C_2
r = 9.37785699191691613941061693063323812472...
p = 0.821619044642187492376904130878969377750...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circs92sq.gif>
The best packing previously known has density p = 0.821619044610 and is not
symmetric.
------------------------------------
David W. Cantrell
> [Previously given improvements for N = 66-68, 78, 79, 84-87 and 100 were
> snipped.]
>