The door width of a simple polygon (a chair) is defined and an O(n2) 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.
ASJC Scopus subject areas
- Control and Systems Engineering
- Computer Science Applications
- Electrical and Electronic Engineering