Pianos are not flat: rigid motion planning in three dimensions

摘要

Consider a robot R that is either a line segment or the Minkowski sum of a line segment and a 3-ball, and a set S of polyhedral obstacles with a total of n vertices in R3. We design near-optimal exact algorithms for planning the motion of R among S when R is allowed to translate and rotate. Specifically, we can preprocess S in time O(n4+e) for any e > 0 into a data structure that given two placements α and β of R, can decide in time O(log n) whether a collision-free rigid motion of R between α and β exists and if so, output such a motion in time asymptotically proportional to its complexity. Furthermore, we can find in time O(n4+e) for any e > 0 the largest placement of a similar (translated, rotated and scaled) copy of R that does not intersect S. A number of additional stronger results are provided. Our line segment motion planning algorithm improves the result of Ke and O'Rourke by two orders of magnitude and almost matches their lower bound, thus settling a classical motion planning problem first considered by Schwartz and Sharir in 1984. This implies a number of natural directions for future work concerning rigid motion planning in three dimensions.