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.
$\begingroup$
$\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$– Joel David HamkinsFeb 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$– RaghavanFeb 25, 2013 at 3:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.)
-
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$– RaghavanFeb 25, 2013 at 2:57