IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Mon, 20 Oct 2014 06:25:24

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 [10], eg. In VLSI design when dividing routing regions into channels [12]. 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.


Goto (at Linköping University): CS Dept TR Overview
<webmaster@ida.liu.se>