Levcopoulos, C. (1986). Fast Heuristic for Minimum Length Rectangular Partitions of Polygons. Technical Report LiTH-IDA-R-86-08, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc. of the Second ACM Symposium on Computational Geometry, Yorktown Heights, New York, June 2-4, 1986. (bibtex),
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]). 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 O(n log n), thus improving the previous O(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.
CS Dept TR Overview