Lower bounds on moving a ladder in two and three dimensions (Q1104091)

It is shown that \(\Omega (n^ 2)\) distinct moves may be necessary to move a line segment (a ``ladder'') in the plane from an initial to a final position in the presence of polygonal obstacles of a total of n vertices, and that \(\Omega (n^ 4)\) moves may be necessary for the same problem in three dimensions. These two results establish lower bounds on algorithms that solve the motion-planning problems by listing the moves of the ladder. The best upper bounds known are \(O(n^ 2 \log n)\) in two dimensions, and \(O(n^ 5 \log n)\) in three dimensions.