首页 | 本学科首页   官方微博 | 高级检索  
     


On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
Authors:Jacob T. Schwartz  Micha Sharir
Abstract: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(n5) 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.
Keywords:
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号