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.

REFERENCES

• 1: Bentley, J. L. and Ottmann, T. A. Algorithms for Reporting and Counting Geometric Intersections, IEEE Trans. Comp. c-28, 9, 1979, 643–647
• 2: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 3: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 4: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 5: Dushnik, B. and Miller, E. W. Partially ordered sets, Am. J. Math. 63 (1941), 600–610

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

General Terms:
Algorithms