Levcopoulos, C. (1986). Minimum Length and "Thickest-First" Rectangular Partitions of Polygons. Technical Report LiTH-IDA-R-86-01, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc.of the 23rd Annual Allerton Conference on Communication, Control and Computing, Monticello, Illinois, October, 1985. (bibtex),
Abstract: Partitioning polygons into rectangles by drawing edges of minimum total length has a variety of applications , eg. In VLSI design when dividing routing regions into channels . In this paper a simple and efficient greedy approximation algorithms is presented and analyzed, and in this way previous result are improved significantly. Roughly, the idea is to draw every time a maximal rectangle whose shortest side is as long as possible. Also, several other related results are announced.
CS Dept TR Overview