Lower bounds on moving a ladder in two and three dimensions

It is shown that (n²) 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 ofn vertices, and that (n⁴) 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 areO(n² logn) in two dimensions, andO(n⁵ logn) in three dimensions.This work was partially supported by NSF Grants DCR-83-51468 and grants from Martin Marietta, IBM, and General Motors.