10
$\begingroup$

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!

$\endgroup$
9
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 9, 2012 at 23:34
  • $\begingroup$ Thank you, John, for recasting my question into such a perspicuous formulation! $\endgroup$ Mar 10, 2012 at 0:39
  • 4
    $\begingroup$ 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? $\endgroup$
    – domotorp
    Mar 10, 2012 at 9:01
  • $\begingroup$ @domotorp: Yes, that viewpoint is somehow clarifying. Thanks! $\endgroup$ Mar 10, 2012 at 16:03
  • 1
    $\begingroup$ Indeed, I am relating your metric to a pole bump metric. My point is that to handle a length 4 rod, I need to bump 4-2=2 poles, and each pole needs two moves to move the rod end around it. This bump metric may lead to a near optimal algorithm where the cost is number of translations and rotations. Gerhard "Excuse Me, I'm Coming Through" Paseman, 2017.03.21. $\endgroup$ Mar 21, 2017 at 15:45

1 Answer 1

10
$\begingroup$

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! :-)

$\endgroup$
1
  • 2
    $\begingroup$ Actually, what you said implies $r\asymp 1/(2L)$ for large $L$ and the details are few, not many. Nice question and cool proof! $\endgroup$
    – fedja
    Mar 22, 2012 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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