n circles in BIG circle
jm bergot
a larger circle with diameter D containing all of them.
What is the minimum diameter D for any n circles? For
example. take circles of diameter 1, 2, 3, 4, and 5 and
find the smallest circle into which they will all fit.
James Waldby
For n < 7, it probably is the case that this can be answered via outer
Soddy circles (see <http://mathworld.wolfram.com/SoddyCircles.html>).
Eg, D(2,3,4) ~ 7.071685, D(3,4,5) ~ 9.001629, D(4,5,6) ~ 11.057543.
Soddy's curvature formula, 2*(a^2+b^2+c^2+d^2) = (a+b+c+d)^2, leads
to d = -(a+b+c - 2*sqrt(a*b+a*c+b*c)), where a...d are reciprocals
of radii. At n=7, D(5,6,7) ~ 13.155990 is too small for the
diameter-4 circle to fit inside with the largest three.
--
jiw
David W. Cantrell
For your example with N = 5, D = 60/(24 sqrt(5) - 47) = 9.001397746...
[What James Waldby said about Soddy circles is correct, but strangely, the
decimal value of D which he gave for N = 5 was a bit too large.]
If I understand correctly, in general, you wish to pack N circular disks of
diameters 1, 2, 3, ... N inside the circle of smallest possible diameter D.
Your question is closely related to that posed in one of Al Zimmermann's
programming contests. See
<http://recmath.com/contest/CirclePacking/index.php>. (Note that links to
figures of the best configurations found during the contest are given in
the final report.)
But if you were expecting a precise general formula for D in terms of N,
then you were expecting too much! Below my signature, I have copied a
posting I made after the conclusion of the contest. That posting gave
approximations for the packing density d in terms of N. But it's easy to
convert info about packing density d into info about your diameter D:
D = sqrt( N (N+1) (2N+1) / (6d) )
David W. Cantrell
-------------------------------------------------
Using the radii provided by JCM at
<http://euler.free.fr/contest/BestSolutions.txt>, the densities of the
packings have been calculated. Additional comments are given below.
The following list begins with the densities of the trivial packings
for N = 1 .. 4, not part of the contest, and then gives the densities
of the best packings found in the contest for N = 5 .. 50:
{1, 0.555556, 0.56, 0.612245, 0.678801, 0.744327, 0.772506, 0.775238,
0.770446, 0.795441, 0.812156, 0.807518, 0.822998, 0.824061, 0.822069,
0.82987, 0.832988, 0.839573, 0.839562, 0.841488, 0.846021, 0.851482,
0.852967, 0.853886, 0.857145, 0.856729, 0.85952, 0.862892, 0.863906,
0.864522, 0.864407, 0.867056, 0.866932, 0.869797, 0.86676, 0.869338,
0.869459, 0.869961, 0.871106, 0.870394, 0.87188, 0.87573, 0.874939,
0.875319, 0.873015, 0.873114, 0.873798, 0.873533, 0.877283, 0.878159}
A plot of the densities of the best packings found for N = 5 .. 50 is
shown at <http://img64.imageshack.us/img64/3141/densitydata3005ov.gif>.
Two curves are also shown there.
The blue curve, 0.899142 - 1.13042/(N + 0.978221), crudely attempts
to approximate the densities.
The red curve, 0.903453 - 1.24430/(N + 2.51683), crudely attempts to
approximate an upper envelope for the data.
Discaimer: I have _no idea_ whether the form, c - k/(N + h), which I
used is actually reasonable or not. Its asymptotic behavior may not
be correct.
The density data and plots can be used to speculate in various ways.
For example, if I were to choose a value of N for which a better
packing could most likely be found, it would be N = 48. [Note: Of
course, I actually suspect that, for _most_ N > 25, better packings
could be found that those found in the contest.]
Here in November, I had conjectured "that there are n, perhaps the
smallest being more than 50, for which
R_best_n < sqrt(n*(n+1)*(2*n+1)/(pi*sqrt(3)))." In other words, I had
conjectured that, eventually, the packing density would exceed the
density of the hexagonal lattice packing for uniform circles in the
plane, which is pi/(2*Sqrt(3)), or 0.9069 approx. Now you may well say
that my own density plots suggest that my conjecture is false, noting
that the constant term c = 0.903453, used in the upper envelope's
approximation, is smaller than pi/(2*Sqrt(3)). But -- recall the note
at the end of the previous paragraph -- I still suspect my conjecture
is correct. (And I think it's abundantly clear now that the smallest
such N, if there is one, is substantially larger than 50.)
James Waldby
> jm bergot <thekin...@yahoo.ca> wrote:
>> You are given n circles each of diameter 1,2,3...n and a larger circle
>> with diameter D containing all of them. What is the minimum diameter D
>> for any n circles? For example. take circles of diameter 1, 2, 3, 4,
>> and 5 and find the smallest circle into which they will all fit.
>
> For your example with N = 5, D = 60/(24 sqrt(5) - 47) = 9.001397746...
> [What James Waldby said about Soddy circles is correct, but strangely,
> the decimal value of D which he gave for N = 5 was a bit too large.]
[...]
Apologies for that! I used only a half-dozen decimal places in
the calculation, and, it appears, only got a 4-digit accuracy.
With 12-digit arithmetic, I get the same 10 digit number you show
above.
--
jiw
jm bergot
this ugly thing I sent in.