Packing many equal small spheres into a large sphere

165 views
Skip to first unread message

Hugo Pfoertner

unread,
May 23, 2006, 6:02:10 PM5/23/06
to
During the last few month I received several requests asking for a
formula to estimate how many spheres of equal size can be packed into a
spherical container. Reasonably good packing results for small sphere
numbers can be seen on the web page (Java needed):

http://www.randomwalk.de/sphere/insphr/spheresinsphr.html

The currently best known radii for n<=72 are given in the table

http://www.randomwalk.de/sphere/insphr/spisbest.txt

Numerical results for larger n are currently not available.
My current recommendation for an heuristic estimate of the number of
equal spheres of radius r that fit into a container of radius R is as
follows:

Calculate relative diameter of small spheres d=r/R.
Relative diameter of core region:

q = 1 - 2*d

Upper limit for number of spheres:

n = (1/d^3) * ( 0.7405*q^3 + 0.484*(1 - q^3) )

Some examples:

d n Best known d
for this n
0.25 33 0.2487624
0.24 38 0.2405156
0.23 43 0.229733
0.22 50 0.2197529
0.21 58 0.2101144
0.2 67 0.2004418
0.19 79
0.18 95
0.17 114
0.16 138
0.15 169
0.14 211
0.13 268
0.12 345
0.11 455
0.1 615
0.09 858
0.08 1242
0.07 1887
0.06 3050
0.05 5368
0.04 10683
0.03 25816
0.02 88867
0.01 725416

d n

0.176863 100
0.0857216 1000
0.0408686 10000
0.01923815 100000
0.00899139 1000000

This assumes an optimally dense packing of the core region and a
heuristically determined lower density for a surface layer. For randomly
packed spheres a more realistic estimate might be obtained by replacing
the Kepler packing density 0.7405 for the core by something like the
value 0.64 found by Jaeger & Nagel.

A comparison with the numerical packing results is shown in
http://www.randomwalk.de/sphere/insphr/nsphisph.gif

For n=60,61 the actually achievable packing density is significantly
higher than predicted by the formula given above.

Hugo Pfoertner

David W. Cantrell

unread,
May 29, 2006, 1:31:58 AM5/29/06
to
Hugo Pfoertner <not...@abouthugo.de> wrote:
> During the last few month I received several requests asking for a
> formula to estimate how many spheres of equal size can be packed into a
> spherical container. Reasonably good packing results for small sphere
> numbers can be seen on the web page (Java needed):
>
> http://www.randomwalk.de/sphere/insphr/spheresinsphr.html
>
> The currently best known radii for n<=72 are given in the table
>
> http://www.randomwalk.de/sphere/insphr/spisbest.txt

Hi Hugo,

Please check the radius which you list for Thierry Gensane's packing of 28
spheres. I suspect that it should actually be 0.2603548 -- in other words,
that perhaps someone transposed a pair of digits. But that's just a guess.
(In the highly unlikely event that 0.2630548 is actually correct, I claim
an improved packing of 27 spheres! ;-)

> Numerical results for larger n are currently not available.
> My current recommendation for an heuristic estimate of the number of
> equal spheres of radius r that fit into a container of radius R is as
> follows:
>
> Calculate relative diameter of small spheres d=r/R.
> Relative diameter of core region:
>
> q = 1 - 2*d
>
> Upper limit for number of spheres:
>
> n = (1/d^3) * ( 0.7405*q^3 + 0.484*(1 - q^3) )

For those who don't recognize it right away, that coefficient of q^3 is
precisely K = pi/(3*sqrt(2)). Based on thinking about asymptotics, I agree
with Hugo that that Kepler packing density must be the correct coefficient
there.

I have devised a simpler formula, closely related to Hugo's, which I
suspect may always give a lower bound for the number of spheres:

n = K*(1 - 2*d)/d^3 + 1/(2*d^2)

In other words, if someone asks "Given d, how many spheres can I pack?",
perhaps a correct answer is "At least floor(K*(1 - 2*d)/d^3 + 1/(2*d^2))
spheres."

> Some examples:

Below, following Hugo's n, I give some n, shown in square brackets, as
produced by my simple conjectured lower bound. Notice however that, for d
less than roughly 0.21, my formula gives n _larger_ than Hugo's. If my
formula does give a lower bound, as conjectured, then some of the best
packings currently known would necessarily be suboptimal. (In particular,
they are the packings for n = 55, 56, 62, 64, 65, 67, 68, 69, 71 and 72
spheres.)

> d n Best known d
> for this n

> 0.25 33 [31] 0.2487624
> 0.24 38 [36] 0.2405156
> 0.23 43 [42] 0.229733
> 0.22 50 [49] 0.2197529
> 0.21 58 [57] 0.2101144
> 0.2 67 [68] 0.2004418


> 0.19 79
> 0.18 95
> 0.17 114
> 0.16 138

> 0.15 169 [175]


> 0.14 211
> 0.13 268
> 0.12 345
> 0.11 455

> 0.1 615 [642]


> 0.09 858
> 0.08 1242
> 0.07 1887
> 0.06 3050
> 0.05 5368
> 0.04 10683
> 0.03 25816
> 0.02 88867

> 0.01 725416 [730670]

Regards,
David W. Cantrell

Hugo Pfoertner

unread,
May 29, 2006, 3:01:18 PM5/29/06
to
"David W. Cantrell" wrote:
>
> Hugo Pfoertner <not...@abouthugo.de> wrote:
> > During the last few month I received several requests asking for a
> > formula to estimate how many spheres of equal size can be packed into a
> > spherical container. Reasonably good packing results for small sphere
> > numbers can be seen on the web page (Java needed):
> >
> > http://www.randomwalk.de/sphere/insphr/spheresinsphr.html
> >
> > The currently best known radii for n<=72 are given in the table
> >
> > http://www.randomwalk.de/sphere/insphr/spisbest.txt
>
> Hi Hugo,
>
> Please check the radius which you list for Thierry Gensane's packing of 28
> spheres. I suspect that it should actually be 0.2603548 -- in other words,
> that perhaps someone transposed a pair of digits. But that's just a guess.
> (In the highly unlikely event that 0.2630548 is actually correct, I claim
> an improved packing of 27 spheres! ;-)

Actually the radius in Thierry Gensane's list for n=28 is
0.2603054756814.

As one can easily see from a comparison between the results found by
Thierry Gensane and my results for n<=50 that many of my results are not
optimal. There is no reason that this should be different beyond n=50.
This gives me some motivation to continue searching for improved
packings, at least after the end of the current round of Al Zimmerman's
programming contest ;-)

BTW, it would be interesting to see a comparison of the estimates from
David's formula against the number of sphere centers inside the Waterman
polyhedra, for which I created some OEIS entries just recently, see
http://www.research.att.com/~njas/sequences/A119869 , the phantastic
Java applet written by Mark Newbold
http://dogfeathers.com/java/ccppoly.html and Paul Bourke's
http://astronomy.swin.edu.au/~pbourke/geometry/waterman/index3.html
(bottom of page).
Since the Waterman polyhedra have an optimally dense packed core from
their construction, the number of spheres inside should be not too far
from the value given by the formula.

Hugo

kiril...@gmail.com

unread,
Feb 3, 2018, 1:14:55 PM2/3/18
to
If i know radius (r) Container (sphere) and radius (r1) of spheres. How Can i find maximum quantity of spheres in Container.

Gerd Thieme

unread,
Feb 4, 2018, 10:21:24 AM2/4/18
to
On Sat, 3 Feb 2018 10:14:46 -0800 (PST), kiril...@gmail.com wrote:

> If i know radius (r) Container (sphere) and radius (r1) of spheres.
> How Can i find maximum quantity of spheres in Container.

⌊2 / (1 + 2⋅q − q²)⌋ where q = r/r1

Solution derived from:
<en.wikipedia.org/wiki/Packing_problems#Spheres_into_a_Euclidean_ball>

Gerd

Robert Delaney

unread,
Feb 4, 2018, 6:04:28 PM2/4/18
to
But, according to that article, that formula for k as the number of
inner spheres only holds if k <= n + 1 where n is the dimension of the
Euclidean space. So for n = 3 it only holds for k <= 4. For more
information look at:

https://en.wikipedia.org/wiki/Sphere_packing_in_a_sphere

Bob



Reply all
Reply to author
Forward
0 new messages