Motion Planning Problems with Boxes: An Introduction for Undergraduate Courses in Discrete Mathematics
Godfried T. Toussaint · 2018
Solutions of simple motion planning problems involving collections of orthogonal rectangles in the plane, and orthogonal boxes in 3-dimensional space are described. Proofs of several theorems regarding collision-free translation properties of these objects are derived. A new elementary simple proof is given that for each quadrant in the plane, every collection of orthogonal rectangles admits precisely one ordering that is valid for collision-free translation of the rectangles in every fixed direction contained in that quadrant. In addition, it is proved that for every configuration of n greater than 3 orthogonal rectangles in the plane, at least four of them have the property that each can be translated independently to infinity in some direction, without disturbing the other n-1 rectangles. The proofs are elementary, and therefore suitable for motivating undergraduate computer science students in courses on discrete mathematics. A list of more challenging advanced problems is also provided.