To ask this question in a (hopefully) more direct way:


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, $S\_c$ (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, $S\_c$, is there a computationally efficient and/or nice way to determine if the ball can ever escape the cage? 




---


Earlier version of question:


In Pachinko one shoots a small metal ball into a forest of pins, then gravity then pulls it downwards so that it will either fall into a pocket (where you win a prize) or the sink at the bottom of the machine. The spacing and distribution of the pins will help to insure that one only wins certain prizes with low probability.


Now imagine that we have a more general game where:


(1) - The ball is simply diffusing in 3-space (like a molecule undergoing Brownian motion). I.e. there is no fixed downward trajectory due to gravity. 


(2) - You win a prize if the ball diffuses over a particular coordinate, just like one of the pockets in regular pachinko.


(3) - We generalize he pins as a set of impassible coordinates.


(4) - We define a 'sink' as an always accessible coordinate.


(5) - We define a starting coordinate for the sphere.


Given access the 3-space coordinates for (2), (3), (4), & (5), what's the most efficient way to find whether the game is 'winnable', or if the ball will fall into the 'sink' with a probability of unity? How can we find the minimum set from (3) that prevents the ball from reaching the pocket?



When can a freely moving sphere escape from a 'cage' defined by a set of impassible coordinates?
Replace the pins by balls of radius $R\_{ball}$ and the ball by a point. This is a logically equivalent formulation. The question, then, is: given a finite set of balls, $B\_1$, $B\_2$, ...., $B\_k$ in $\mathbb{R}^n$, and a point $x$, how to determine where $x$ is in the unbounded component of $\mathbb{R}^n \setminus \bigcup B\_i$.


I don't know the answer to this, but here is an easy way to compute the number of connected components of $\mathbb{R}^n \setminus \bigcup B\_i$. In other words, I can determine whether there is some place from which a ball cannot escape. 


By [Alexander duality](http://en.wikipedia.org/wiki/Alexander_duality), the number of bounded components of $\mathbb{R}^n \setminus \bigcup B\_i$ this is the dimension of $H\_n(\bigcup B\_i)$. 


Cover $\bigcup B\_i$ by the $B\_i$. Every intersection of finitely many $B\_i$ is convex, hence contractible. So $\bigcup B\_i$ is homotopic to the nerve of this cover. That is a simplicial complex, so it is easy to compute its homology.


One final practical idea: I have used painting software where I could click on a point and it would color every point which was connected to that one. Maybe the algorithms used to make that software could solve this problem as well?


