-- Packing circles in semicircles: new results
David W. Cantrell
packing problem. But, inspired by David Alan Paterson, Eckard Specht added
a section, <http://hydra.nat.uni-magdeburg.de/packing/csc/csc.html>,
concerning that type of packing to Packomania on July 23. Since then, I
have found a few improved packings, which will be presented in this thread.
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. Most packings are asymmetric;
those having symmetry group D_1 will be so indicated. (Also note that, when
comparing my packings with those shown at Packomania, my radius r is that
of the semicircle enclosing N unit circles, and therefore my radius r
corresponds with Packomania's "ratio".)
------------------------------------
N = 24
r = 7.92208131918612568011...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circ24semic.gif>
The best packing previously known has r = 7.92233...
------------------------------------
N = 35
r = 9.45328039825511110710...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circ35semic.gif>
The best packing previously known has r = 9.45339...
and symmetry group D_1.
------------------------------------
N = 72
r = 13.31428901033464563283...
symmetry group D_1
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circ72semic.gif>
The best packing previously known has r = 13.31428901054...
and symmetry group D_1.
------------------------------------
David W. Cantrell
David W. Cantrell
circles in semicircles.
N = 37
r = 9.68835012163100207686...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circ37semic.gif>
The best packing previously known has r = 9.6883518...
------------------------------------
N = 42
r = 10.35025463086142147668...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circ42semic.gif>
The best packing previously known has r = 10.35061...
------------------------------------
N = 45
r = 10.67614501785795553785...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circ45semic.gif>
The best packing previously known has r = 10.6761494...
------------------------------------
N = 52
r = 11.38783722729115488037...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circ52semic.gif>
The best packing previously known has r = 11.387850...
David W. Cantrell
semicircle is given.
N = 41
r = 10.254005592590933056594...
symmetry group D_1
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circ41semic.gif>
The best packing previously known has r = 10.2564...
Walter Christie
Dear David W. Cantrell:
I have a question having specifically to do with this thread. I noticed you typed "--" at the beginning of the Subject line of your original post. What was your purpose in doing so and what would the implications be of not doing so?
Thank you,
Walt
David W. Cantrell
> Dear David W. Cantrell:
>
> I have a question having specifically to do with this thread. I noticed
> you typed "--" at the beginning of the Subject line of your original
> post. What was your purpose in doing so and what would the implications
> be of not doing so?
Using "--" was suggested at one time in order to help distinguish nonspam
posts from spam.
At least for a while, Ken Pledger's "Welcome to <sci.math>. These
suggestions may help you." posts recommended using "--". But, after you
asked your question, I looked at Ken's most recent post of that type, which
appeared today, and saw that the recommendation to use "--" no longer
appears. I suppose that my using "--" is now outdated, and so I will cease
that practice henceforth.
David
David W. Cantrell
are given.
N = 60
r = 12.27248377687578077183...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circ60semic.gif>
The best packing previously known has r = 12.2735...
------------------------------------
>
> N = 72
> r = 13.31428901033464563283...
> symmetry group D_1
>
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circ72semic.gif>
>
> The best packing previously known has r = 13.31428901054...
> and symmetry group D_1.
>
> ------------------------------------
N = 83
r = 14.27726167664516351605...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circ83semic.gif>
The best packing previously known has r = 14.27754...
------------------------------------
David W. Cantrell
David W. Cantrell
semicircles are given.
All packings which have previously appeared in this thread (N = 24, 35, 37,
41, 42, 45, 52, 60, 72, 83) are now presented at Packomania and so, below,
only the three new packings are listed now.
> David W. Cantrell <DWCan...@sigmaxi.net> wrote:
> Packing N unit circles in the smallest possible semicircle is not a
> classic packing problem. But, inspired by David Alan Paterson,
> Eckard Specht added a section,
> <http://hydra.nat.uni-magdeburg.de/packing/csc/csc.html>, concerning
> that type of packing to Packomania on July 23. Since then, I have found
> a few improved packings, which will be presented in this thread.
>
> 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. Most packings are
> asymmetric; those having symmetry group D_1 will be so indicated. (Also
> note that, when comparing my packings with those shown at Packomania,
> my radius r is that of the semicircle enclosing N unit circles, and
> therefore my radius r corresponds with Packomania's "ratio".)
------------------------------------
N = 78
r = 13.88502403975392945061...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circ78semic.gif>
The best packing previously known has r = 13.8863...
------------------------------------
N = 94
r = 15.16549891891487588453...
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circ94semic.gif>
The best packing previously known has r = 15.1710...
------------------------------------
N = 129
r = 17.58753524651564786343...
symmetry group D_1
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circ129semic.gif>
The best packing previously known has r = 17.5875365...
------------------------------------
David W. Cantrell
Phil Carmody
> In this post, improved packings of 78, 94 and 129 unit circles in
> semicircles are given.
What kind of facilities are you using to perform these calculations?
Is it the kind of thin where an individual cvolunting a single PC for
a couple of months could make a positive contribution, or do you have
entire Uni labs dedicated to the task?
Phil
--
If GML was an infant, SGML is the bright youngster far exceeds
expectations and made its parents too proud, but XML is the
drug-addicted gang member who had committed his first murder
before he had sex, which was rape. -- Erik Naggum (1965-2009)
David W. Cantrell
in semicircles are given, for N = 68, 77, 79, 87, 88, 91, 95, 97, 99, 101
and 145.
Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
> What kind of facilities are you using to perform these calculations?
A single PC, several years old, used to search for improved packings when
it's not being used otherwise. And for software, Mathematica together with
MathOptimizer Professional.
> Is it the kind of thin where an individual cvolunting a single PC for
> a couple of months could make a positive contribution,
Yes indeed. ("cvolunting" ?)
Some of the best packings previously known do not actually give local
minima for the radius, and so several of the improvements below were
obtained merely by "tightening" previously known configurations until local
minima were reached. Taking the improvements below into account, I suspect
that almost all of the configurations for N <= 101 now represent local
minima. But of course, whether those minima are global is an entirely
different matter, and I suspect that quite a few of them are not.
------------------------------------
N = 68
r = 12.97995404559455136951...
The best packing previously known has r = 12.979954054...
------------------------------------
N = 77
r = 13.76438981940291275284...
The best packing previously known has r = 13.764392...
------------------------------------
N = 79
r = 13.97439210678549389128...
The best packing previously known has r = 13.97439227...
------------------------------------
N = 87
r = 14.61365897456286836423...
The best packing previously known has r = 14.6144...
------------------------------------
N = 88
r = 14.67575735563974155284...
The best packing previously known has r = 14.67575735587...
------------------------------------
N = 91
r = 14.91066543313212351489...
The best packing previously known has r = 14.91066543377...
------------------------------------
N = 95
r = 15.24926705201405180740...
The best packing previously known has r = 15.2492696...
------------------------------------
N = 97
r = 15.42287633990370670208...
The best packing previously known has r = 15.4264...
------------------------------------
N = 99
r = 15.53876966653260562339099445348627900166153647604...
The best packing previously known has r = 15.5387696665326056233909944535
Since that agrees with my radius, if rounded off, you may wonder how the
previous packing and mine differ. My packing has four more contacts than
the packing now shown at
<http://hydra.nat.uni-magdeburg.de/packing/csc/csc99.html>. Specifically,
in my packing (and referring to the numbering shown in my figure), 42
touches 34 and 37, 51 touches 45, and 59 touches 53. This makes circles 42,
51 and 59 a part of a large hexagonal lattice. In the previous packing,
those four tangencies were absent and so the three circles were not quite a
part of the large hexagonal lattice, causing the radius of the semicircle
to have exceeded my radius by some minute amount.
------------------------------------
N = 101
r = 15.65956998543784425546...
The best packing previously known has r = 15.659576...
------------------------------------
N = 145
r = 18.64788542479464526032...
The best packing previously known has r = 18.6761...
------------------------------------
David W. Cantrell
David W. Cantrell
for N = 65 and 73.
------------------------------------
N = 65
r = 12.69574653724841625412...
The best packing previously known has r = 12.6999...
------------------------------------
N = 73
r = 13.44313759769290495851...
The best packing previously known has r = 13.4515...
------------------------------------
David W. Cantrell
Phil Carmody
> in semicircles are given, for N = 68, 77, 79, 87, 88, 91, 95, 97, 99, 101
> and 145.
>
> Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
>> What kind of facilities are you using to perform these calculations?
>
> A single PC, several years old, used to search for improved packings when
> it's not being used otherwise. And for software, Mathematica together with
> MathOptimizer Professional.
Yikes. That's one way of limitting your potential target audience.
>> Is it the kind of thin where an individual cvolunting a single PC for
>> a couple of months could make a positive contribution,
>
> Yes indeed. ("cvolunting" ?)
Yikes, no idea where that came from. Alas I have no machine running
mathematica, so can't contribute.
Is your code potentially portable to something free?
David W. Cantrell
> David W. Cantrell <DWCan...@sigmaxi.net> writes:
> > Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
> >> What kind of facilities are you using to perform these
> >> calculations?
> >
> > A single PC, several years old, used to search for improved
> > packings when it's not being used otherwise. And for software,
> > Mathematica together with MathOptimizer Professional.
>
> Yikes. That's one way of limitting your potential target audience.
But using those programs is not necessary. Probably, almost nobody else who
does packings uses that combination; most don't even use any computer
algebra system.
> >> Is it the kind of thing where an individual [using] a single PC
> >> for a couple of months could make a positive contribution,
> >
> > Yes indeed.
>
> Alas I have no machine running mathematica, so can't contribute.
>
> Is your code potentially portable to something free?
Not mine. But most people who do packings have code that should be portable
to something free. Dave Boll had a program which could be downloaded at one
time, but I don't know if it's still available.
I've recently found eight more improved packings of N unit circles in
semicircles, for N = 64, 69, 70, 71, 92, 98, 105 and 137. Unfortunately, at
the moment, I'm having a computer problem which is preventing me from
generating figures of these new packings. Below, I give the data without
figures; I expect to solve the computer problem and provide links to
figures of these packings tomorrow.
------------------------------------
N = 64
r = 12.60775500930766654162...
The best packing previously known has r = 12.60790...
------------------------------------
N = 69
r = 13.05703665490987444333...
The best packing previously known has r = 13.05712...
------------------------------------
N = 70
r = 13.14839232959363200778...
The best packing previously known has r = 13.14843...
------------------------------------
N = 71
r = 13.23865404008107577084...
The best packing previously known has r = 13.23878...
------------------------------------
N = 92
r = 14.99219043044003355714...
The best packing previously known has r = 14.99291...
------------------------------------
N = 98
r = 15.49021047623555193545...
The best packing previously known has r = 15.49066...
------------------------------------
N = 105
r = 15.93987811204481072033...
The best packing previously known has r = 15.939878167...
------------------------------------
N = 137
r = 18.10332073619026020001...
The best packing previously known has r = 18.103320780...
------------------------------------
David W. Cantrell
David W. Cantrell
> I've recently found eight more improved packings of N unit circles in
> semicircles, for N = 64, 69, 70, 71, 92, 98, 105 and 137. Unfortunately,
> at the moment, I'm having a computer problem which is preventing me from
> generating figures of these new packings. Below, I give the data without
> figures; I expect to solve the computer problem and provide links to
> figures of these packings tomorrow.
Links to figures of these eight packings have now been inserted below.
------------------------------------
N = 64
r = 12.60775500930766654162...
The best packing previously known has r = 12.60790...
------------------------------------
N = 69
r = 13.05703665490987444333...
The best packing previously known has r = 13.05712...
------------------------------------
N = 70
r = 13.14839232959363200778...
The best packing previously known has r = 13.14843...
------------------------------------
N = 71
r = 13.23865404008107577084...
The best packing previously known has r = 13.23878...
------------------------------------
N = 92
r = 14.99219043044003355714...
The best packing previously known has r = 14.99291...
------------------------------------
N = 98
r = 15.49021047623555193545...
The best packing previously known has r = 15.49066...
------------------------------------
N = 105
r = 15.93987811204481072033...
The best packing previously known has r = 15.939878167...
------------------------------------
N = 137
r = 18.10332073619026020001...
David W. Cantrell
for N = 38, 82, 85, 86 and 110.
------------------------------------
N = 38
r = 9.85164063747353471362...
The best packing previously known has r = 9.8520...
------------------------------------
N = 82
r = 14.20218995130687710827...
The best packing previously known has r = 14.20220...
------------------------------------
N = 85
r = 14.44360616629781899036...
The best packing previously known has r = 14.4448...
------------------------------------
N = 86
r = 14.53224586981196755371...
The best packing previously known has r = 14.5339...
------------------------------------
N = 110
r = 16.28887329387400561818...
The best packing previously known has r = 16.28895...
------------------------------------
David W. Cantrell
David W. Cantrell
57, 58, 63, 96 and 100.
(This post likely concludes any improvements which I can make for N < 100.)
------------------------------------
N = 56
r = 11.87194185978469615009...
The best packing previously known has r = 11.871962...
------------------------------------
N = 57
r = 11.96872033484538165544...
The best packing previously known has r = 11.9692...
------------------------------------
N = 58
r = 12.06186805111745872761...
The best packing previously known has r = 12.06199...
------------------------------------
N = 63
r = 12.51520836717166716308...
The best packing previously known has r = 12.5160...
------------------------------------
N = 96
r = 15.34969643338087748158...
The best packing previously known has r = 15.3500...
------------------------------------
N = 100
r = 15.61901303363832060528...
The best packing previously known has r = 15.61915...
------------------------------------
David W. Cantrell
David W. Cantrell
N = 186 and 232, following a comment about why packing unit circles in
a _semicircle_ is an atypical packing problem.
This probably concludes my involvement in this thread, but there are many
improvements yet to be made for N > 100 at
<http://hydra.nat.uni-magdeburg.de/packing/csc/csc.html>.
------------------------------------
Packing unit circles in a semicircle is an unusual type of packing problem
At Packomania's page about packing circles in circles, Eckard Specht says
"You know that there is an equivalence between the following two problems:
i) packing of N circles in a container, and ii) spreading of N points in a
container."
Well, in case you didn't already know that is true when the container is a
commonly used one, such as a circle or a square, think about it! The crux
of the matter is that a parallel curve to the inside of such commonly used
containers has precisely the same shape as the container itself. In other
words, that parallel curve _is similar to_ the container.
But that is not true when the container is a semicircle. For that reason,
i) packing N unit circles in a semicircle and ii) spreading N points in a
semicircle are not equivalent problems.
There is, however, a packing problem which is equivalent to optimally
spreading N points in a semicircle: Packing N unit circles in a Norman
window having a base rectangle of unit height. (I've never seen this
problem considered.)
------------------------------------
N = 186
r= 20.99553967105736393268...
symmetry group D_1
The best packing previously known has r = 21.005...
------------------------------------
N = 232
r = 23.36674485356207051839...
The best packing previously known has r = 23.399...
Readers might notice that the new packing is very close to being symmetric.
The only part where it's easy to see asymmetry is near the top of the
semicircle. But in fact the large group of circles in a hexagonal lattice
is shifted horizontally so that it is very slightly off center. This sort
of thing happens fairly often, it seems, in optimizing packings of circles
in semicircles.
------------------------------------
David W. Cantrell,
who will probably now return to the classic
problem of packing unit circles in squares