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!

Improve this question
$\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$
    – John Wiltshire-Gordon
    Commented Mar 9, 2012 at 23:34
  • $\begingroup$ Thank you, John, for recasting my question into such a perspicuous formulation! $\endgroup$
    – Joseph O'Rourke
    Commented 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
    Commented Mar 10, 2012 at 9:01
  • $\begingroup$ @domotorp: Yes, that viewpoint is somehow clarifying. Thanks! $\endgroup$
    – Joseph O'Rourke
    Commented 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$
    – Gerhard Paseman
    Commented Mar 21, 2017 at 15:45

1 Answer 1

Reset to default
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! :-)

Improve this answer
$\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
    Commented Mar 22, 2012 at 15:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .