Premium
On the “piano movers'” problem I. The case of a two‐dimensional rigid polygonal body moving amidst polygonal barriers
Author(s) -
Schwartz Jacob T.,
Sharir Micha
Publication year - 1983
Publication title -
communications on pure and applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.12
H-Index - 115
eISSN - 1097-0312
pISSN - 0010-3640
DOI - 10.1002/cpa.3160360305
Subject(s) - bounded function , mathematics , motion (physics) , three body problem , rigid body , robotics , time complexity , geometry , combinatorics , computer science , mathematical analysis , artificial intelligence , robot , classical mechanics , physics
We present an algorithm that solves a two‐dimensional case of the following problem which arises in robotics: Given a body B , and a region bounded by a collection of “walls”, either find a continuous motion connecting two given positions and orientations of B during which B avoids collision with the walls, or else establish that no such motion exists. The algorithm is polynomial in the number of walls ( O ( n 5 ) if n is the number of walls), but for typical wall configurations can run more efficiently. It is somewhat related to a technique outlined by Reif.