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

Let every point of $\mathbb{Z}^2$ be surrounded by a mirrored disk of radius $r < \frac{1}{2}$, except leave the origin $(0,0)$ unoccupied by a disk.

Q. Is it the case that every disk can be hit by a lightray emanating from the origin and reflecting off the mirrored disks?

Lightrays are composed of (infinitely thin) segments, and reflect off the disks with angle of incidence equal to angle of reflection. For example, here is one way (of many ways) to hit the $(0,2)$ disk when $r = \frac{1}{4}$ with two reflections; it clearly cannot be reached directly, with zero reflections:
PinballAll

I believe the answer to my question Q is Yes, but I would be grateful for confirmation from the dynamical systems experts. (Forgive me if I have not learned sufficently from my previous, related question, "Pinball on the infinite plane.")

It occurs to me it might be interesting to color the disks according to the minimum number of reflections needed to hit each...

share|improve this question
    
Does it matter what happens to a ray that hits a disk tangentially? –  Joel Reyes Noche Apr 20 '13 at 1:14
    
@Joel: Good question! It seems the most natural assumption is that the ray continues beyond the tangency along the same trajectory. That accords with angle of incidence = angle of reflection. –  Joseph O'Rourke Apr 20 '13 at 1:26

4 Answers 4

Let $C_r(x,y)$ or $C(x,y)$ be the circle of radius $r$ about the lattice point $(x,y)$.

Suppose we choose a sequence of circles to hit, and ask for the piecewise linear path of shortest length from the origin hitting each of the circles along the path. If this doesn't go inside a circle, then by the least action principle, the angle of incidence will equal the angle of reflection.

We can run into problems in two ways. First, the line segments can intersect other circles. For example, if we ask the path to visit $C(1,0)$ and then $C(3,0)$, then the line segment must intersect $C(2,0)$. So, we better restrict the paths not to do that. Second, the shortest piecewise linear path may pass through the interior of a circle. For example, from the origin to $C(1,1)$ to $C(2,2)$, the shortest path passes through the interior of $C(1,1)$. Again, to avoid this, we'll restrict the paths.

If $r$ is close to $1/2$, then you will need to bounce back and forth several times between adjacent circle to squeeze by them. However, for smaller $r$, we can construct a viable path more simply. Suppose $r \lt \sqrt{2}/4 \approx 0.354$. Then no line segment connecting $C_r(x,y)$ to $C_r(x+1,y+1)$ passes through any other circle. Consequently, from any point on $C_r(x,y)$ to any point on $C_r(x+1,y+1)$, the shortest path which hits $C_r(x+1,y)$ does not go inside $C_r(x+1,y)$, it is a piecewise linear path which reflects off of $C_r(x+1,y)$.

Take a path from $(0,0)$ to $(x,y)$ with unit steps parallel to the axes so that each step is perpendicular to the previous. Without loss of generality, we can assume $0 \le x \le y$, and we can walk to $(0,1), (1,1), (1,2), ... (x,x)$. From there, we use a sawtooth pattern: $(x,x+1), (x-1,x+1),(x-1,x+2),(x,x+2),(x,x+3),(x-1,x+3)... (x,y)$. Then the shortest curve starting at the origin which hits the circles centered at these points in this order is a piecewise linear path of a light ray which reaches $C(x,y)$ by reflecting off the circles in that order.


Sawtooth
               (Image added by J.O'Rourke)

This only handled $r \lt \sqrt{2}/4$. I believe that you can cover the case of $\sqrt{2}/4 \le r \lt 1/2$ by replacing $C(x,y) \to C(x+1,y)$ with $C(x,y)\bigg( \to C(x+1,y) \to C(x,y)\bigg)^n \to C(x+1,y)$, where the number of repetitions $n$ depends on $r$, perhaps $n=c/(1/2-r)$.

share|improve this answer
1  
@Douglas: I took the liberty of illustrating your clever idea. –  Joseph O'Rourke Apr 20 '13 at 21:06
3  
Can you just say: the shortest piecewise linear path from the origin to the desired point where all the segments start and end on discs, and don't path through other discs. It's clear that there are such paths. Now, can we show that there is a shortest one by using compactness? –  Peter Shor Apr 20 '13 at 21:57
2  
@Peter Shor: Nice, that simplifies things a lot. The limit of paths which don't pass through the interior of a disc also will not pass through the interior of that disc. So the set of paths which don't go too far is compact. A possible problem is that the limit of non-tangencies may become tangent. However, you can restrict the paths which are allowed so that there will never be a tangency as a limit. –  Douglas Zare Apr 20 '13 at 23:46

Douglas Zare's shortest path idea seems to me very well-suited for this.

Intuitively, we can view the circles as being rings, and the reflected ray like a rope going through the rings. We pull to obtain the shortest rope (considering the rings fixed, and other suitable idealizations).

The picture below shows how a path connecting $(0,0)$ with $C(m,n)$ may be. Normally, one should be able to calculate the precise contact points and the reflection angles, from the initial angle and $r$, but I am too lazy to do this.

alt text

Added

Douglas Zare's comment, that when the radius is close to $1/2$, the things get more difficult, is right, as it can be seen from the illustration provided by Joseph O'Rourke in another answer. So here's how I think we can use the solution I presented above, to handle any possible $r<1/2$.

Start with the above solution, which works for, say, $r_0=1/3$. If $r<1/3$, one can decrease the radii of the circles, until the desired radius is reached, without aby problem. The solution will still hold. The difficulties appear if the radius is larger. We gradually increase the radii of the circles, until the string becomes tangent to at least a circle. Then, we wrap once again the string. We continue to gradually increase the radius, and when the string becomes tangent, wrap it more, until we get the desired radius. The two main cases we can encounter with the solution I presented above, along with the proposed "moves", are represented below.

alt text

share|improve this answer
    
Nice analogy: a taut rope through rings! But wouldn't the rope detach from rings when pulled taut, and wrap around some tangentially...? –  Joseph O'Rourke Apr 27 '13 at 15:40
    
@Joseph O'Rourke: The rope goes through the ring, so it can't detach. At least in the solution I pictured, which connects $(0,0)$ with any $(m,n)$. –  Cristi Stoica Apr 27 '13 at 17:19
    
:-) $\mbox{} \mbox{}$ –  Joseph O'Rourke Apr 27 '13 at 18:41
    
That's a nice picture, but it relies on the radius not being too close to $1/2$. Roughly radius is needed for that picture to work? –  Douglas Zare Apr 27 '13 at 22:51
    
I've added an illustration of near-$\frac{1}{2}$ radii (in another "answer"). –  Joseph O'Rourke Apr 28 '13 at 0:22

I add this image just to illustrate that matters seem more complicated (as Douglas Zare has emphasized) when the radii of the disks approaches $\frac{1}{2}$:
          alt text

share|improve this answer

For small radii r, perhaps r less than 1/5, something like the following should work. I use symmetry to restrict my attention to circles in the first quadrant.

Use a checkerboard coloring and color the origin and circles with coordinates of like parity the same color, e.g silver. It should be clear that any silver circle with coordinate (0,n) or (1,n) is reachable by using n-1 reflections, and that at least 120 degrees of arc on that circle is reachable.

Now one can cover larger x coordinates by reflecting the ray off (0,n) and going up. Although the ray does not emanate from the center of (0,n), it should be clear that there is enough of the or spectrum of angles to choose from that one can use an additional reflection to hit, say, (2,n) after leaving (0,n). This should generalize to an arbitrary silver circle, and each such has at least 120 degrees of arc as an available target.

Once all the silver circles are shown to be reachable, construct a path to an arbitrary circle (m,n) by traversing to (0,n) or (0,n+1), which ever is silver, go up to a silver circle past but near (m,n), and reflect off a silver circle to the desired target.

Gerhard "Loopy After Bouncing Off Walls" Paseman, 2013.04.19

share|improve this answer
    
Tilting my head 45 degres, it looks like r can even be slightly larger than 1/root(8) for this construction to work. For r close to 1/2, something different is needed. Gerhard "Easier Than Tilting The Picture" Paseman, 2013.04.19 –  Gerhard Paseman Apr 20 '13 at 2:00
    
I like the phrase, "spectrum of angles"! –  Joseph O'Rourke Apr 20 '13 at 2:19
    
Where do you use the "120 degrees" condition? I see it mentioned twice as something to be satisfied, but it never seems to be applied. –  S. Carnahan Apr 22 '13 at 0:19
    
In using the silver circles, I normally just have a small portion of arc that is needed when I am travelling horizonally only or vertically only. When I change directions (or when I need to go to a neighboring nonslver circle), instead of needing access to a few degrees of arc, I need access to more than 90 degrees off of a silver circle, as to have the flexibility of bouncing off either the left or the right side of that circle. If I plan my route, I actually need less than 20 degrees, even when r is a little more than 1/root(5). Gerhard "Ask Me About System Design" Paseman, 2013.04.21 –  Gerhard Paseman Apr 22 '13 at 4:46

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.