1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 25, 2013 at 2:34
  • $\begingroup$ 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? $\endgroup$
    – Raghavan
    Feb 25, 2013 at 3:05

1 Answer 1

1
$\begingroup$

An analogous process to the one you describe is known as Apollonian sphere packing:
      http://www.scivis.ethz.ch/research/projects/packing_problems/apoll3D.png?hires (Image from this link.)

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Raghavan
    Feb 25, 2013 at 2:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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