Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
Do you have particular (typical) values for the relative sizes of your ball and the pockets/pins/sinks? Have you thought about the 2D version? –  Yemon Choi Apr 21 '10 at 19:58
    
Dear Yemon, I'm interested in the general problem more than a version where the balls/pins are of a particular size (the size of the pocket and sink doesn't matter to me because I only want to know if the ball can ever reach the 'winning' pocket). However, I can say that the size of the ball should be smaller than the largest distance between any two pins or impassible coordinates. –  Rob Grey Apr 21 '10 at 20:13
    
For the two-dimensional case, I'm attempting a solution by generating polygons to encapsulate the 'winning' pocket, whose vertices consist of the pins/impassible coordinates, and where the maximum side-length is less that the cross-sectional diameter of the ball. The idea would be to increase the number of possible sides of the polygon, and length of the neighborhood around the 'winning' pocket, over time during the search. –  Rob Grey Apr 21 '10 at 20:19
    
I found "diffusing" to be a confusing word choice, and changed it to "moving". This seems like a problem which can be solved using Voronoi diagrams. I suggest asking it also on stackoverflow; not that it is inappropriate here, but there may be more computational geometry people on SO. –  Reid Barton Apr 22 '10 at 22:05
add comment

2 Answers

up vote 15 down vote accepted

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?

share|improve this answer
    
The ideas in this excellent answer are similar to those used by Baryshnikov et al in the talk slides I posted. –  j.c. Apr 22 '10 at 22:39
    
What a fantastic answer! –  Rob Grey Apr 22 '10 at 23:30
    
This is a beautiful answer. –  Tom Church Apr 23 '10 at 0:38
add comment

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 does include some discussion of computing the possibility of caging / linking effectively, but again, they focus on the 2D problem.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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