Fast heuristics for minimum length rectangular partitions of polygons

ABSTRACT

We consider the problem of partitioning isothetic polygons into rectangles by drawing edges of minimum total length. The problem has various applications [LPRS], eg. in VLSI design when dividing routing regions into channels ([Riv1], [Riv2]). If the polygons contain holes, the problem in NP-hard [LPRS]. In this paper it is shown how solutions within a constant factor of the optimum can be computed in time &Ogr;(n log n), thus improving the previous &Ogr;(n2) time bound. An unusual divide-and-conquer technique is employed, involving alternating search from two opposite directions, and further efficiency is gained by using a fast method to sort subsets of points. Generalized Voronoi diagrams are used in combination with plane-sweeping in order to detect all “well bounded” rectangles, which are essential for the heuristic.

REFERENCES

• ChewD: L. Paul Chew , Robert L. (Scot) Dyrsdale, III, Voronoi diagrams based on convex distance functions, Proceedings of the first annual symposium on Computational geometry, p.235-244, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323264]
• Fort: Steven Fortune, A Fast Algorithm for Polygon Containment by Translation (Extended Abstract), Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.189-198, July 15-19, 1985
• GonZ: Teofilo Gonzalez , Si-Qing Zheng, Bounds for partitioning rectilinear polygons, Proceedings of the first annual symposium on Computational geometry, p.281-287, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323269]
• ImAs: Imai, H., and Asano, T., "Dynamic intersection Search with Applications", Proc. 25th iEEE FOCS Symp., Florida, 1984.
• KeilS: Keil, J.M., and J.R. Sack, "Minimum Decompositions of Polygonal Objects", SCS-TR-42, Carleton University, Ottawa.
• Kirk: Kirkpatrick, D.G., "An upper bound for sorting integers in restricted ranges", Proc. 18th Allerton Conf. on Comm. Control and Computing, Illinois, (Oct. 1980).
• Lev1: Levcopoulos, C., "Minimum Length and 'Thickest- First' Rectangular Partitions of Polygons", Proc. 23rd Allerton Conf. on Comm. Control and Computing, Illinois, October 1985.
• Lev2: Levcopoulos, C., "Heuristics for Decomposing Polygons into Rectangles" (preliminary title), in prepara~ tion, LinkSping.
• LevLin: Christos Levcopoulos , Andrzej Lingas, Bounds on the Length of Convex Partitions of Polygons, Proceedings of the Fourth Conference on Foundations of Software Technology and Theoretical Computer Science, p.279-295, December 13-15, 1984
• Lin: Andrzej Lingas, Heuristics for minimum edge length rectangular partitions of rectilinear figures, Proceedings of the 6th GI-Conference on Theoretical Computer Science, p.199-210, January 05-07, 1983
• Lloyd: Lloyd, E.L., "On Triangulations of a Set of Points in the Plane", Proc. of 18th IEEE Conf. on Foundations of Comp. Sc., Providence, 1977.
• LPRS: Lingas, A., R.Y. Pinter, R.L. Rivest, and A. Shamir, "Minimum Edge Length Partitioning of Rectilinear Polygons", Proc. 20th Allerton Conf. on Comm. Control and Compt., Illinois, 1982.
• PrepS: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• Riv1: Ronald L. Rivest, The “PI” (placement and interconnect) system, Proceedings of the 19th conference on Design automation, p.475-481, January 1982
• Riv2: Rivest, R., Private Communication, October 1985.

INDEX TERMS

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  I.3 COMPUTER GRAPHICS
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Region growing, partitioning

General Terms:
Algorithms, Performance, Theory, Verification