Partitioning rectilinear figures into rectangles

ABSTRACT

This paper discusses the problem of partitioning rectilinear regions, with or without holes, into a minimum number of rectangles. An algorithm which solves this partitioning problem in time O(n5/2), where n is the number of vertices of the rectilinear figure, is presented.

REFERENCES

• 1: J.E. Hopcroft, R.M. Karp, An n~'2 algorithm for maximum matchings in bipartite graphs, SIAM Journal of Computing 2 (1973), pp. 225-231.
• 2: D. S. Johnson, The NP-completeness column : An ongoing guide, Journal of Algorithms, 3 (1982), pp. 182-195.
• 3: J. M. Keil, Decomposing a polygon into simpler components, SIAM Journal on Computing, 14, 4 (1985), pp. 799-817.
• 4: J M Keil, Minimally covering a horizontally convex orthogonal polygon, Proceedings of the second annual symposium on Computational geometry, p.43-51, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10520]
• 5: W. Lipski, E. Lodi, F. Luccio, C. Mugnai, L, Pagli, On twodimensional data organization I, Fundamenta Informaticae, 2 (t978), pp. 211-226.
• 6: W. Lipski, E. Lodi, F. Luccio, C. Mugnai, L. Pagli, On twodimensional data organization II, Fundamenta Informaticae, 2 (1978), pp. 245-260.
• 7: J. O'Rourke, K. J. Supowit, Some NP-hard polygon decomposition problems, IEEE trans, on Information Theory, vol. IT-29, 2 (1983), pp. 181-190.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching; Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Design, Performance, Theory, Verification