Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let's say, I have a closed 3D surface (say, the surface of a pebble). I want to pack it with spheres, but starting with the largest possible sphere, then the next largest possible non-overlapping sphere and so on until I reach a specified lower limit on sphere size. Is there a unique solution? Is this a known, solved problem? Is there an obvious algorithmic approach to do this? Please advice. I am not in applied math or computational geometry, but love to wet my feet in these fine fields.

share|improve this question
1  
It can't be unique in general. For example, the original volume may have rotational symmetries, which the packed versions do not respect. For some packings, one may have a choice of where to put the currently-largest-fitting sphere, and this choice may rule out other choices that might have been valid. –  Joel David Hamkins Feb 25 '13 at 2:34
    
I see. Thanks. I was thinking of a particular approach. Please opine if you think it is reasonable. Say, my surface shape is defined by polygons. I can find all the voronoi spheres (allowing overlaps) in it. Then I start with the largest voronoi sphere contained inside my surface, then pick the next largest non-overlapping voronoi sphere and so on working my way down. Wouldn't that be a reasonably robust approach - even if I can't prove it is THE best collection? Are there better alternative approaches to that? –  Raghavan Feb 25 '13 at 3:05

1 Answer 1

An analogous process to the one you describe is known as Apollonian sphere packing:
      (Image from this link.)

share|improve this answer
1  
Thank you for the response. Apollonian sphere packing sure comes close (I hadn't heard of it before), but I feel it is not quite. For example, if the pebble IS a sphere, then the approach I am looking for will result in a single sphere, but the Apollonian sphere packing will result in numerous ones, wouldn't it? My goal is to use the sizes and numbers of the spheres packed inside my pebble-like close surface (packed using the protocol I mention - start with largest sphere and work my way down to a specified minimum sized sphere) to make sense of the surface's shape. –  Raghavan Feb 25 '13 at 2:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.