On translating a set of rectangles

Abstract

Given a collection of disjoint objects in the plane, we are interested in translating them by a common vector. If we have a primitive for translating one object at a time, then the order in which the objects can individually be translated is often geometrically constrained. In this paper we study the nature of these constraints and exhibit optimal algorithms for finding valid motion ordering for several different classes of objects. These algorithms find use in computer display applications.