How to Move a Chair Through a Door

Chee Keng Yap

doi:10.1109/JRA.1987.1087093

How to Move a Chair Through a Door

Chee Keng Yap

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English (US)
Pages (from-to)	172-181
Number of pages	10
Journal	IEEE Journal on Robotics and Automation
Volume	3
Issue number	3
DOIs	https://doi.org/10.1109/JRA.1987.1087093
State	Published - Jun 1987

ASJC Scopus subject areas

Control and Systems Engineering
General Engineering
Computer Science Applications
Electrical and Electronic Engineering

Access to Document

10.1109/JRA.1987.1087093

Cite this

@article{ee771e488c4248f7807185ec02bffa3e,

title = "How to Move a Chair Through a Door",

abstract = "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.",

author = "Yap, {Chee Keng}",

note = "Funding Information: Manuscript received July 3, 1986; revised November 6, 1986. This work was supported in part by NSF grants #DCR-84-01898 and #DCR-84-01633. The author is with the Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY 10012, USA. IEEE Log Number 8714995. I The interested reader may refer to Strang{\textquoteright}s paper for the amusing genesis of the problem.",

year = "1987",

month = jun,

doi = "10.1109/JRA.1987.1087093",

language = "English (US)",

volume = "3",

pages = "172--181",

journal = "IEEE Journal on Robotics and Automation",

issn = "0882-4967",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}

TY - JOUR

T1 - How to Move a Chair Through a Door

AU - Yap, Chee Keng

N1 - Funding Information: Manuscript received July 3, 1986; revised November 6, 1986. This work was supported in part by NSF grants #DCR-84-01898 and #DCR-84-01633. The author is with the Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY 10012, USA. IEEE Log Number 8714995. I The interested reader may refer to Strang’s paper for the amusing genesis of the problem.

PY - 1987/6

Y1 - 1987/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0023363697&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023363697&partnerID=8YFLogxK

U2 - 10.1109/JRA.1987.1087093

DO - 10.1109/JRA.1987.1087093

M3 - Article

AN - SCOPUS:0023363697

SN - 0882-4967

VL - 3

SP - 172

EP - 181

JO - IEEE Journal on Robotics and Automation

JF - IEEE Journal on Robotics and Automation

IS - 3

ER -

How to Move a Chair Through a Door

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this