How to move a chair through a door

We define the door-width of a simple polygon (a ´chair´) and give an O(n²) algorithm for computing its door-width. It is first shown that all passages of the chair through the door can be reduced to a sequence of certain elementary motions. We introduce the technique of constraint analysis in characterizing elementary motions. 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.