Prev: Delayed differential equation
Next: Ordered computation of eigenvalues from good initial estimates, without explicit sorting
From: David W. Cantrell on 25 Apr 2010 10:43
Improved packings of N unit circles in squares are given for N = 67,
135 and 149. With those improvements: For N <= 150, no packings
remain which are obviously suboptimal.

We also discuss, following the new packing for N = 67, a problem
which arises when only numerics are used to determine whether
circles touch.

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

N = 67
s = 15.97764930297533545113885511637259843819916521187...
136 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/
circs67sq.gif>

The best packing previously known is one which was posted earlier
in this thread. Its side length is larger than that of the new packing
by 7.7 * 10^-47. It has the same number of contacts as the new
packing.

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

A problem with numerically determining whether circles touch

Example 1 (N = 160):

Consider the second figure at
<http://hydra.nat.uni-magdeburg.de/packing/csq/csq160.html>,
showing a packing of 160 unit circles in a square. Circles #114,
120, 121, 129 and 135 are all depicted as being part of
a hexagonal lattice. Yet circle #128 is shown as touching both
circles #120 and 135, but _not_ touching circles #114 and 121.
This is a geometric impossibility! No such packing can exist.
If circles #114, 120, 121, 129 and 135 were all truly in a
hexagonal lattice and circle #128 touches both circles #120
and 135, then circle #128 would necessarily also touch circles
#114 and 121.

The cause of the problem:
In fact, circle #135 is not actually part of the hexagonal lattice
which includes circles #114, 120, 121 and 129. Rather, circle #135 is
very slightly separated from circle #129 (and thus the total number
of contacts is 365, instead of 366). Eckard's program, which I believe
currently uses 30 significant digits, considered unit circles #129
and 135 as touching because the distance between them is so small:
roughly 2 * 10^-36.

To solve this problem for this packing with N = 160, one could, of
course, use more significant digits. But presumably, for general N,
using any fixed number of significant digits will be inadequate to
determine precisely which circles touch or not.

Example 2 (N = 67):

<http://hydra.nat.uni-magdeburg.de/packing/csq/csq67.html>
currently shows my previous packing for N = 67. Note that
circle #40, shown in cyan, is indicated as having only two
contacts. But of course, any circle having only two contacts could be
repositioned so that it has no contacts, that is, it must actually be
a "rattler". And since, when counting the total number of contacts in
a packing, it is desirable and customary that only _necessary_
contacts be counted, the number of contacts in my previous packing is
actually 136, rather than 138. Of course, the source of the problem is
the same as in example 1. But here the consequence of the problem is
less severe, merely incorrectly inflating the number of contacts,
rather than producing a geometric impossibility.

My new packing for N = 67, which has a different circle as a rattler,
will again have its number of contacts incorrectly inflated if 30
significant digits are used. If the rattler near the right side of the
square (circle #55 in my figure at the Photobucket link above) were
positioned to maximize its distance from the three nearest unit
circles, that distance would be only about 2 * 10^-44. Using 30
significant digits, not only would the number of contacts be inflated
by three, but the rattler would be shown as being fixed (having three
spurious contacts) and thus lead to another geometric impossibility.
Instead, in the data which I will send to Eckard, I will position that
rattler so that, just as for my previous packing for N = 67 as shown
at Packomania, using 30 significant digits will cause only two
unnecessary contacts to be indicated.

The moral:
For my packings, the figures given in the links in this thread
(together with the number of contacts reported here) should be
considered definitive. Of course I hope that, eventually, the
information at Packomania will be in complete agreement with the
information in this thread. But that may not be achieved easily or
soon.

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

N = 135
s = 22.50670793867788263154...
261 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/
circs135sq.gif>

The best packing previously known has side length
s = 22.506707938691... and 241 contacts.

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

N = 149
s = 23.66759560234166323610...
328 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/
circs149sq.gif>

The best packing previously known has side length
s = 23.66759582... and 282 contacts.

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

David W. Cantrell
From: David W. Cantrell on 25 Apr 2010 17:44
Improved packings of N unit circles in squares are given for N = 151,
153 and 155-158.

Earlier today, I had written:
> Improved packings of N unit circles in squares are given for N = 67,
> 135 and 149. With those improvements: For N <= 150, no packings
> remain which are obviously suboptimal.
>
> We also discuss, following the new packing for N = 67, a problem
> which arises when only numerics are used to determine whether
> circles touch.
>
> ------------------------------------
>
> N = 67
> s = 15.97764930297533545113885511637259843819916521187...
> 136 contacts
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs67sq.gif>
>
> The best packing previously known is one which was posted earlier
> in this thread. Its side length s is larger than that of the new packing
> by 7.7 * 10^-47. It has the same number of contacts as the new
> packing.
>
> ------------------------------------
>
> A problem with numerically determining whether circles touch

More examples of this problem are noted below, when discussing the new
packings for N = 155 and 157.

> Example 1 (N = 160):
>
> Consider the second figure at
> <http://hydra.nat.uni-magdeburg.de/packing/csq/csq160.html>,
> showing a packing of 160 unit circles in a square. Circles #114,
> 120, 121, 129 and 135 are all depicted as being part of
> a hexagonal lattice. Yet circle #128 is shown as touching both
> circles #120 and 135, but _not_ touching circles #114 and 121.
> This is a geometric impossibility! No such packing can exist.
> If circles #114, 120, 121, 129 and 135 were all truly in a
> hexagonal lattice and circle #128 touches both circles #120
> and 135, then circle #128 would necessarily also touch circles
> #114 and 121.
>
> The cause of the problem:
> In fact, circle #135 is not actually part of the hexagonal lattice
> which includes circles #114, 120, 121 and 129. Rather, circle #135 is
> very slightly separated from circle #129 (and thus the total number
> of contacts is 365, instead of 366). Eckard's program, which I believe
> currently uses 30 significant digits, considered unit circles #129
> and 135 as touching because the distance between them is so small:
> roughly 2 * 10^-36.
>
> To solve this problem for this packing with N = 160, one could, of
> course, use more significant digits. But presumably, for general N,
> using any fixed number of significant digits will be inadequate to
> determine precisely which circles touch or not.
>
> Example 2 (N = 67):
>
> <http://hydra.nat.uni-magdeburg.de/packing/csq/csq67.html>
> currently shows my previous packing for N = 67. Note that
> circle #40, shown in cyan, is indicated as having only two
> contacts. But of course, any circle having only two contacts could be
> repositioned so that it has no contacts, that is, it must actually be
> a "rattler". And since, when counting the total number of contacts in
> a packing, it is desirable and customary that only _necessary_
> contacts be counted, the number of contacts in my previous packing is
> actually 136, rather than 138. Of course, the source of the problem is
> the same as in example 1. But here the consequence of the problem is
> less severe, merely incorrectly inflating the number of contacts,
> rather than producing a geometric impossibility.
>
> My new packing for N = 67, which has a different circle as a rattler,
> will again have its number of contacts incorrectly inflated if 30
> significant digits are used. If the rattler near the right side of the
> square (circle #55 in my figure at the Photobucket link above) were
> positioned to maximize its distance from the three nearest unit
> circles, that distance would be only about 2 * 10^-44. Using 30
> significant digits, not only would the number of contacts be inflated
> by three, but the rattler would be shown as being fixed (having three
> spurious contacts) and thus lead to another geometric impossibility.
> Instead, in the data which I will send to Eckard, I will position that
> rattler so that, just as for my previous packing for N = 67 as shown
> at Packomania, using 30 significant digits will cause only two
> unnecessary contacts to be indicated.
>
> The moral:
> For my packings, the figures given in the links in this thread
> (together with the number of contacts reported here) should be
> considered definitive. Of course I hope that, eventually, the
> information at Packomania will be in complete agreement with the
> information in this thread. But that may not be achieved easily or
> soon.
>
> ------------------------------------
>
> N = 135
> s = 22.50670793867788263154...
> 261 contacts
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs135sq.gif>
>
> The best packing previously known has side length
> s = 22.506707938691... and 241 contacts.
>
> ------------------------------------
>
> N = 149
> s = 23.66759560234166323610...
> 328 contacts
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs149sq.gif>
>
> The best packing previously known has side length
> s = 23.66759582... and 282 contacts.
>
> ------------------------------------

N = 151
s = 23.82251439160247719965...
359 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs151sq.gif>

The best packing previously known has side length
s = 23.8225143937... and 319 contacts.

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

N = 153
s = 24.01021876668148648296...
353 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs153sq.gif>

The best packing previously known has side length
s = 24.01021876673... and 319 contacts.

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

N = 155
s = 24.13241594484677182538...
358 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs155sq.gif>
(Note: In the figure above, the distance between unit circles #106 and
118 is sufficiently small, only about 2 * 10^-29, that, when this packing
appears at Packomania, those circles might be shown as touching, with the
total number of contacts being given as 359.)

The best packing previously known has side length
s = 24.1324159487... and 295 contacts.

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

N = 156
s = 24.21344528296218157944...
369 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs156sq.gif>

The best packing previously known has side length
s = 24.2134452832... and 368 contacts.

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

N = 157
s = 24.25986239435024781231...
365 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs157sq.gif>
(Note: In the figure above, circle #128 is a rattler. But, regardless
of how it is positioned, the distances between it and five nearby circles
are so small that, using 30 significant digits, it will seem to touch the
five nearby circles. Thus it can be expected that, when this packing
appears at Packomania, that rattler will be shown as fixed and the total
number of contacts will be given as 370.)

The best packing previously known has side length
s = 24.25986239455... and 313 contacts.

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

N = 158
s = 24.295613378688153058231782520700...
315 contacts
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs158sq.gif>

The best packing previously known has side length
s = 24.29561337868815305823178270... and 292 contacts.

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

David W. Cantrell
From: christian.bau on 25 Apr 2010 17:45
On Apr 25, 10:44 pm, David W. Cantrell <DWCantr...(a)sigmaxi.net> wrote:

Out of curiosity: These packings are obviously quite hard to find. Has
anyone tried, either for real or using some simulation, how close to
these results one would get with purely mechanical models? For
example, you mention N = 158, s = 24.295613378688153058231782520700...
If I took 158 very smooth coins with a radius of 1 cm, and built a box
of side s = 24.3, height 50 cm, and a moveable lid, and then I pressed
the lid down, would I have a decent chance to fit all the coins into a
box of 24.3 x 24.3? What if I press the lid down and simultaneously
shake the box? Or if I build a square box with two moveable sides that
move simultaneously, so that the box is always square. Would I come
close to your best result, or would I have to be very lucky to come
anywhere near?

Say I build a square box of size 50 x 50, put 158 coins inside at
random positions, and slowly move the left and top side
simultaneously, so that the coins move according to the laws of
physics, until nothing moves. What size would I end up with?
From: ThomasCR on 26 Apr 2010 11:52
On Apr 25, 11:44 pm, David W. Cantrell <DWCantr...(a)sigmaxi.net> wrote:
> Improved packings of N unitcirclesin squares are given for N = 151,
> 153 and 155-158.
>
> Earlier today, I had written:
>
>
>
> > Improved packings of N unitcirclesin squares are given for N = 67,
> > 135 and 149. With those improvements: For N <= 150, no packings
> > remain which are obviously suboptimal.
>
> > We also discuss, following the newpackingfor N = 67, a problem
> > which arises when only numerics are used to determine whether
> >circlestouch.
>
> > ------------------------------------
>
> > N = 67
> > s = 15.97764930297533545113885511637259843819916521187...
> > 136 contacts
> > <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs67....>
>
> > The bestpackingpreviously known is one which was posted earlier
> > in this thread. Its side length s is larger than that of the newpacking
> > by 7.7 * 10^-47. It has the same number of contacts as the new
> >packing.
>
> > ------------------------------------
>
> > A problem with numerically determining whethercirclestouch
>
> More examples of this problem are noted below, when discussing the new
> packings for N = 155 and 157.
>
>
>
> > Example 1  (N = 160):
>
> > Consider the second figure at
> > <http://hydra.nat.uni-magdeburg.de/packing/csq/csq160.html>,
> > showing apackingof 160 unitcirclesin a square.Circles#114,
> > 120, 121, 129 and 135 are all depicted as being part of
> > a hexagonal lattice. Yet circle #128 is shown as touching both
> >circles#120 and 135, but _not_ touchingcircles#114 and 121.
> > This is a geometric impossibility! No suchpackingcan exist.
> > Ifcircles#114, 120, 121, 129 and 135 were all truly in a
> > hexagonal lattice and circle #128 touches bothcircles#120
> > and 135, then circle #128 would necessarily also touchcircles
> > #114 and 121.
>
> > The cause of the problem:
> > In fact, circle #135 is not actually part of the hexagonal lattice
> > which includescircles#114, 120, 121 and 129. Rather, circle #135 is
> > very slightly separated from circle #129 (and thus the total number
> > of contacts is 365, instead of 366). Eckard's program, which I believe
> > currently uses 30 significant digits, considered unitcircles#129
> > and 135 as touching because the distance between them is so small:
> > roughly 2 * 10^-36.
>
> > To solve this problem for thispackingwith N = 160, one could, of
> > course, use more significant digits. But presumably, for general N,
> > using any fixed number of significant digits will be inadequate to
> > determine precisely whichcirclestouch or not.
>
> > Example 2  (N = 67):
>
> > <http://hydra.nat.uni-magdeburg.de/packing/csq/csq67.html>
> > currently shows my previouspackingfor N = 67. Note that
> > circle #40, shown in cyan, is indicated as having only two
> > contacts. But of course, any circle having only two contacts could be
> > repositioned so that it has no contacts, that is, it must actually be
> > a "rattler". And since, when counting the total number of contacts in
> > apacking, it is desirable and customary that only _necessary_
> > contacts be counted, the number of contacts in my previouspackingis
> > actually 136, rather than 138. Of course, the source of the problem is
> > the same as in example 1. But here the consequence of the problem is
> > less severe, merely incorrectly inflating the number of contacts,
> > rather than producing a geometric impossibility.
>
> > My newpackingfor N = 67, which has a different circle as a rattler,
> > will again have its number of contacts incorrectly inflated if 30
> > significant digits are used. If the rattler near the right side of the
> > square (circle #55 in my figure at the Photobucket link above) were
> > positioned to maximize its distance from the three nearest unit
> >circles, that distance would be only about 2 * 10^-44. Using 30
> > significant digits, not only would the number of contacts be inflated
> > by three, but the rattler would be shown as being fixed (having three
> > spurious contacts) and thus lead to another geometric impossibility.
> > Instead, in the data which I will send to Eckard, I will position that
> > rattler so that, just as for my previouspackingfor N = 67 as shown
> > at Packomania, using 30 significant digits will cause only two
> > unnecessary contacts to be indicated.
>
> > The moral:
> > For my packings, the figures given in the links in this thread
> > (together with the number of contacts reported here) should be
> > considered definitive. Of course I hope that, eventually, the
> > information at Packomania will be in complete agreement with the
> > information in this thread. But that may not be achieved easily or
> > soon.
>
> > ------------------------------------
>
> > N = 135
> > s = 22.50670793867788263154...
> > 261 contacts
> > <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs13....>
>
> > The bestpackingpreviously known has side length
> > s = 22.506707938691... and 241 contacts.
>
> > ------------------------------------
>
> > N = 149
> > s = 23.66759560234166323610...
> > 328 contacts
> > <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs14....>
>
> > The bestpackingpreviously known has side length
> > s = 23.66759582... and 282 contacts.
>
> > ------------------------------------
>
> N = 151
> s = 23.82251439160247719965...
> 359 contacts
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs15...>
>
> The bestpackingpreviously known has side length
> s = 23.8225143937... and 319 contacts.
>
> ------------------------------------
>
> N = 153
> s = 24.01021876668148648296...
> 353 contacts
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs15...>
>
> The bestpackingpreviously known has side length
> s = 24.01021876673... and 319 contacts.
>
> ------------------------------------
>
> N = 155
> s = 24.13241594484677182538...
> 358 contacts
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs15...>
> (Note: In the figure above, the distance between unitcircles#106 and
> 118 is sufficiently small, only about 2 * 10^-29, that, when thispacking
> appears at Packomania, thosecirclesmight be shown as touching, with the
> total number of contacts being given as 359.)
>
> The bestpackingpreviously known has side length
> s = 24.1324159487... and 295 contacts.
>
> ------------------------------------
>
> N = 156
> s = 24.21344528296218157944...
> 369 contacts
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs15...>
>
> The bestpackingpreviously known has side length
> s = 24.2134452832... and 368 contacts.
>
> ------------------------------------
>
> N = 157
> s = 24.25986239435024781231...
> 365 contacts
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs15...>
> (Note: In the figure above, circle #128 is a rattler. But, regardless
> of how it is positioned, the distances between it and five nearbycircles
> are so small that, using 30 significant digits, it will seem to touch the
> five nearbycircles. Thus it can be expected that, when thispacking
> appears at Packomania, that rattler will be shown as fixed and the total
> number of contacts will be given as 370.)
>
> The bestpackingpreviously known has side length
> s = 24.25986239455... and 313 contacts.
>
> ------------------------------------
>
> N = 158
> s = 24.295613378688153058231782520700...
> 315 contacts
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs15...>
>
> The bestpackingpreviously known has side length
> s = 24.29561337868815305823178270... and 292 contacts.
>
> ------------------------------------
>
> David W. Cantrell

Some new results with a new packing program at http://critticall.com/SQU_cir.html
From: David W. Cantrell on 27 Apr 2010 11:24
"christian.bau" <christian.bau(a)cbau.wanadoo.co.uk> wrote:
> On Apr 25, 10:44=A0pm, David W. Cantrell <DWCantr...(a)sigmaxi.net> wrote:
>
> Out of curiosity: These packings are obviously quite hard to find. Has
> anyone tried, either for real or using some simulation, how close to
> these results one would get with purely mechanical models?

Hello, Christian,

Yes, such simulations have certainly been used.

> For example, you mention N = 158,
> s = 24.295613378688153058231782520700... If I took 158 very smooth coins
> with a radius of 1 cm, and built a box of side s = 24.3, height 50 cm,
> and a moveable lid, and then I pressed the lid down, would I have a
> decent chance to fit all the coins into a box of 24.3 x 24.3?

That depends on what you consider to be a "decent chance". But even if you
specified that, I don't know the answer. My guess is that the chance would
be indecent. :-)

> What if I press the lid down and simultaneously shake the box?

Of course, that would improve your chance considerably. There are computer
programs which simulate that.

Only a few days ago did I finally get a copy of _New Approaches to Circle
Packing in a Square_, P.G. Szabo et al. (Springer, 2007). Once I've had a
chance to digest certain parts of it, I'll be making comments about it in
this thread. But now concerning your question:

p. 44
5.3 Billiard simulation
This method was used by Graham and Lubachevsky, for example.

p. 45
5.4 Pulsating Disk Shaking (PDS) algorithm
"... it is well known that good packings were achieved in 3D by real
physical shaking of balls. Thus the PDS algorithm itself is based on a more
physically motivated 'shake-and-rattle' concept." (BTW, the book includes a
CD containing code for this algorithm.)

> Or if I build a
> square box with two moveable sides that move simultaneously, so that the
> box is always square. Would I come close to your best result, or would I
> have to be very lucky to come anywhere near?

Again, I don't really know the answer. But I'd guess that, with many
trials, you might have a good chance.

> Say I build a square box of size 50 x 50, put 158 coins inside at
> random positions, and slowly move the left and top side
> simultaneously, so that the coins move according to the laws of
> physics, until nothing moves. What size would I end up with?

Again, I don't really know.

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