An algorithm for constructing regions with rectangles: Independence and minimum generating sets for collections of intervals

ABSTRACT

We provide an algorithm which solves the following problem: given a polygon with edges parallel to the x and y axes, which is convex in the y direction, find a minimum size collection of rectangles, which cover the polygon and are contained within it. The algorithm is quadratic in the number of vertices of the polygon. Our method also yields a new proof of a recent duality theorem equating minimum size rectangle covers to maximum size sets of independent points in the polygon.

REFERENCES

• 1: S. Chaiken, D.J. Kleitman, M. Saks, J. Shearer; "Covering Regions by Rectangles," SIAM J. Alg. Disc. Meth. (2), Dec. 1981, pp. 394-410.
• 2: E. Györi; "A Minimax Theorem of New Type," 1983, to appear.
• 3: W.J. Masek; "Some NP-complete set covering problems," 1978, unpublished manuscript, M.I.T.
• 4: E.L. Lawler; Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, 1976.
• 5: M. Aigner; Combinatorial Theory, Springer-Verlag, 1979.
• 6: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 7: T. Asano and T. Asano; "Minimum Partition of Polygonal Regions," 24th Symposium on Foundations of computer Science (Nov., 1983) IEEE Computer Soc., pp. 233-241.
• 8: T. Ohtsuki; "Minimum Dissection of Rectilinear Regions," Proc. IEEE Int. Symposium on Circuits and Systems (Rome, 1982) pp. 1210-1213.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Performance, Theory