0

I would like to know if there is a formula, or at least some bounds, for the following problem. Consider a (three-dimensional) sphere of radius R. What is the maximum number of equal spheres, all of radius r less than R, that I can put on the surface of the large sphere without having the small spheres overlap? The arrangement need not be regular. That is, the requirements are 1. that the centers of the small spheres are all at R+r from the center of the large central sphere; and 2. that the centers of the small spheres are at least 2r apart from each other. I have googled quite a bit and came across various papers about the kissing number (which is a more restricted problem) and spherical codes, but if I understand it correctly, the latter is not quite the problem I consider, because the minimum distance is to be maximized rather than minimized.

TomR
  • 133
  • 1
  • 14
  • 3
    Try asking this question in math.stackexchange.com – Peter O. Dec 20 '19 at 00:52
  • Thanks for the suggestion, I have done so now: https://math.stackexchange.com/questions/3482675/maximum-number-of-non-overlapping-spheres-covering-a-sphere – TomR Dec 20 '19 at 11:05

1 Answers1

1

This is more math than programming (so I voted for Close) ... unless you want this as a bound for bin packing ...

Anyway handle this as comment and not as an answer (but as comment this would not be readable)

if you want just approximate bound and not exact number you can divide the large sphere surface by average density of the smaller spheres/circles coverage...

So: all the small spheres centers are placed at sphere r+R surface. The surface is:

S = 4*PI*(r+R)^2

now if we place smaller spheres (r) tightly on flat plane it would look like this:

hexagonal circle packing

Now when compare the gaps (green) area to square-disc (red) area:

The gaps are formed just by equilateral triangles and 60deg pie areas:

gap

pie:            PI*r^2/6 
triangle:       sqrt(3/4)*r^2/2
triangular gap: tri - 3*(pie-tri)
                4*tri - 3*pie
                4*sqrt(3/4)*r^2/2 - 3*PI*r^2/6 
                2*sqrt(3/4)*r^2 - PI*r^2/2
                sqrt(3)*r^2 - PI*r^2/2
                r^2*(sqrt(3) - PI/2)

so now just divide placement area sphere(r+R) by coverage area.

Each equilateral triangle of side 2*r will cover 3/6 of a disc(r) with single triangular gap so:

n =  S(sphere(R+r)) / 2*S(triangle(2*r)
n = 4*PI*(r+R)^2 / ( 2*sqrt(3/4)*(2*r)^2/2 )
n = PI*(r+R)^2 / sqrt(3/4)*r^2
n = ~ floor (3.6275987*(1+(R/r))^2)

Beware its not exact number as I simplified the problem a lot (by assuming sphere surface instead of polygon created from centers of smaller spheres) but should be pretty close to the real bound and the more precise if r<<R ...

btw here slightly related QAs that might be of interest:

Btw. you can attack this from the other end (using the Sphere triangulation link).

the best packing of spheres on sphere have the centers placed on equilateral triangles. So if you start with ICOSAHEDRON and sub divide it you will get the number of vertex ... small spheres on a big sphere where you compute r and R from the result. and recursively subdivide until R/r matches your wanted R'/r'

So with each iteration the R/r will go closer to yours R'/r' and once the ratio is crossed (it will go further away from it) you stop and have your wanted n (count of vertexes of the closest result) ...

Spektre
  • 49,595
  • 11
  • 110
  • 380