When can a freely moving sphere escape from a ‘cage’ defined by a set of impassible coordinates?

Question

Hopefully there are some computational geometry folks here who can help me out with the following problem -

Please imagine that I take a freely moving ball in 3-space and create a 'cage' around it by defining a set of impassible coordinates, Sc (i.e. points in 3-space that no part of the diffusing ball is allowed to overlap). These points reside within the volume, V(cage), of some larger sphere, where V(cage) >> V(ball).

Provided the set of impassible coordinates, Sc, is there a computationally efficient and/or nice way to determine if the ball can ever escape the cage?

Please see my earlier post at MathOverflow - http://mathoverflow.net/questions/21911/when-can-a-freely-moving-sphere-escape-from-a-cage-defined-by-a-set-of-impassib

Answer 1

Say the ball has radius R. As your friends over at MathOverflow have noted, the problem is equivalent to replacing the impassible points with balls of radius R, and the ball with a point P. So the question is whether P is in a chamber sealed off by the balls.

To answer this question, you need to compute the union of the balls, then take the surface S of this union. If P is inside any of the components of S, it will be trapped, otherwise it can escape.

The are well established algorithms for computing the union of balls, dating back to at least this paper by EdelsBrunner. There's quite a bit of learning curve to understanding and implementing that algorithm, but fortunately it is implemented in the CGAL library.

Once CGAL has calculated the skin,you can look at the connected components of the skin (all of which should be closed meshes) and check whether P is inside any of them (if you need help with that, shout).

Since the tessellated skin is an approximation of the actual sphere surfaces, you may ask whether there are precision problems. I would expect the mesh faces to actually be inside the original balls, and assuming P was originally outside of all the balls, I think that checking whether P is inside any of the skin components will give you accurate results.