Lower bounds on moving a ladder in two and three dimensions |
| |
Authors: | Yan Ke Joseph O'Rourke |
| |
Institution: | (1) Department of Computer Science, Johns Hopkins University, 21218 Baltimore, MD, USA |
| |
Abstract: | It is shown that (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 ofn vertices, and that (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 areO(n
2 logn) in two dimensions, andO(n
5 logn) in three dimensions.This work was partially supported by NSF Grants DCR-83-51468 and grants from Martin Marietta, IBM, and General Motors. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|