Bounds for partitioning rectilinear polygons

ABSTRACT

We study the problem of partitioning a rectilinear polygon with interior points into rectangles by introducing a set of line segments. All points must be included in at least one of the line segments introduced and the objective function is to introduce a set of line segments such that the sum of their lengths is minimal. Since this problem is computationally intractable, we present efficient approximation algorithms for its solution. The solutions generated by our algorithms are guaranteed to be within a fixed constant of the optimal solution value. Even though the constant approximation bound is not so small, we conjecture that in general the solutions our algorithms generate are close to optimal.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: [AT] Avis, D. and G. T. Toussaint, An Efficient Algorithm for Decomposing a Polygon into Star-shaped Polygons, Pattern Recognition, Vol. 13, 1981.
• 3: Bernard Chazelle , David Dobkin, Decomposing a polygon into its convex parts, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.38-48, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804396]
• 4: [GJPT] Garey, M. R., D. S. Johnson, F. P. Preparata and R. E. Tarjan, Triangulating a Simple Polygon; Information Processing Letters, Vol. 7, No. 4, (June 1978).
• 5: [GZ] Gonzalez, T. and S-Q. Zheng, Approximation Algorithms for Partitioning Rectilinear Polygons, Technical Report, University of California, Santa Barbara, March 1985.
• 6: [LLMP] Lodi, E., F. Luccio, C. Mugnai, and L. Pagli, On Two-dimensional Data Organization I; Fundamenta Informaticae, Vol. 2, No. 2 (1979).
• 7: [LLMPL] Lodi, E. F. Luccio, C. Mugnai, L. Pagli and W. Lipski, Jr., On Two-dimensional Data Organization II; Fundamenta Informaticae, Vol. 2, No. 3 (1979).
• 8: [LPRS] Lingas, A. R. Y. Pinter, R. L. Rivest, and A. Shamir, Minimum Edge Length Partitioning of Rectilinear Polygons, Proc. 20th Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, Oct. 1982.
• 9: Ronald L. Rivest, The “PI” (placement and interconnect) system, Proceedings of the 19th conference on Design automation, p.475-481, January 1982
• 10: [S] Sack, J. R. An O(n log n) Algorithm for Decomposing Simple Rectilinear Polygons into Convex Quadrilaterals, Proc. 20th Annual Allerton Conference on Communication, Control and Computing, Oct. 1982.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

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

Keywords:
approximation algrithms, partition of rectilinear polygons, polynomial time complexity