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

Question

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?

Answer 1

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, 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?

Answer 2

I recently heard a beautiful talk by Yuliy Baryshnikov on the general question of when an object can be pinned by some set of fixed points. They consider arbitrary objects in 2D and prove the following theorem:

Let D be a planar domain. Either one can pull a configuration C of two points $\{p_1,p_2\}$ around D, or there exists a full rotation of C entirely within D, that is a loop π′: $S^1$ → E (E being the Euclidean group of transformations) such that the vector $π′\circ p_1 − π′ \circ p_2$ turns around the origin (perhaps, several times).

They use a topological approach which uses Mayer-Vietoris sequences in homology; apparently to generalize to 3D one must use Mayer-Vietoris spectral sequences, though this is "future work".

The slides are here and do include some discussion of computing the possibility of caging / linking effectively, but again, they focus on the 2D problem.