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

Imagine an object, which I'll call a ladder $\cal{L}$, a "racetrack" shape composed of a rectangle of length $L$ capped at either end by semicircles of radius $r$; so it is $L+2r$ tip-to-tip. View every lattice point of $\mathbb{Z}^2$ as a point obstacle (a pole). The ladder is forbidden to include a pole in its interior, but $\cal{L}$ may touch poles on its boundary. $\cal{L}$ is initially sitting in the plane in a horizontal orientation.
          Ladder Thin
My question is:

Q. Under what conditions on $L \ge 0$ and $r \le \frac{1}{2}$can $\cal{L}$ be reoriented via continuous motions to a vertical orientation?

Throughout the motions, no pole may be interior to $\cal{L}$.

If $L=0$, $\cal{L}$ is a disk of radius $r$; if $r=0$, $\cal{L}$ is a segment of length $L$.

I believe that, for $r=0$, there is no upper bound on $L$: an arbitrarily long segment can be reoriented. (I made this an exercise (7.3) in a textbook.) And certainly when $r=\frac{1}{2}$, and, say $L=1$, reorientation is not possible. I can see that, for $r=\frac{1}{2}$, any $L \le \sqrt{2}-1$ can be reoriented (because then $\cal{L}$ fits inside a circle of radius $\sqrt{2}/2$). Almost everything else is unclear to me.
                    Ladder Fat

An analogous question may be posed for an appropriately defined "ladder" amidst $\mathbb{Z}^d$ obstacles.

Any insights, even for specific $(L,r)$ values, or corrections to my beliefs above, are welcomed. Thanks!

share|improve this question
    
Each legal position of the ladder can be described by the location of its center and its angle relative to the x-axis. Further, we do not mind translations by the integer lattice. This means that the configuration space of ladders is some closed semi-algebraic subset of the torus T^3. We are trying to understand the connected components. –  John Wiltshire-Gordon Mar 9 '12 at 23:34
    
Thank you, John, for recasting my question into such a perspicuous formulation! –  Joseph O'Rourke Mar 10 '12 at 0:39
3  
Of course the problem is equivalent to rotating a segment of length L with radius r obstacle-discs around each lattice point, for me its more natural to think about it this way. A natural upper bound on L is that it must fit in any angle - is this not sufficient? –  domotorp Mar 10 '12 at 9:01
    
@domotorp: Yes, that viewpoint is somehow clarifying. Thanks! –  Joseph O'Rourke Mar 10 '12 at 16:03
    
What are the values of $L$ and $r$ for the shape in the 15-move diagram? –  Gerry Myerson Mar 21 '12 at 22:00
show 1 more comment

1 Answer

At the EuroCG conference that ended as I post this, Sándor Fekete (Braunschweig) solved this question modulo a few details, with useful input from Günter Rote (Berlin). Sándor's crucial observation is that, when the ladder is in an extreme configuration, it is touching three lattice points, which form an empty lattice triangle, which by Pick's Theorem, has area $\frac{1}{2}$, so the $L \times r$ rectangle has area 1, and so $r \sim 1/L$. There are many details to convert this to a formal proof, but it seems this insight yields the right dependency between $r$ and $L$ to allow reorientability.

Curiously, at the conference a banquet bus was forced to execute a maneuver not dissimilar from the 15-move back-&-forth path illustrated in my first figure! :-)

share|improve this answer
2  
Actually, what you said implies $r\asymp 1/(2L)$ for large $L$ and the details are few, not many. Nice question and cool proof! –  fedja Mar 22 '12 at 15:14
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.