How to move a chair through a door

摘要

The door width of a simple polygon (a chair) is defined and an O(n^{2}) algorithm for computing its door width is given. It is first shown that all passages of the chair through the door can be reduced to a sequence of certain elementary motions. The technique of constraint analysis in characterizing elementary motions is introduced. Our algorithm actually constructs a motion of the chair through a door, and thus is a "local expert" for planning motion through doors. Such algorithms have applications in more general motion-planning systems in robotics.