Levcopoulos, C. (1986). A fast Heuristic for Covering Polygons by Rectangles. Technical Report LiTH-IDA-R-86-03, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc. of Int. Conf. on Fundamentals of Computation Theory (FCT'85), Cottbus, GDR, September 1985 and in Lecture Notes in Computer Science No 199. (bibtex),
Abstract: During the fabrication of masks for integrated circuits, the polygons on the pattern generator must be covered by a preferably as small as possible number of rectangles. In this paper we present a fast and simple heuristic, based on Voronoi diagrams, which covers arbitrary polygons without acute interior angles by rectangles in time 0(nlog+r), where n is the number of edges of the polygon and r is the number, in practice close to n, of rectangles produced, and they suggest that the algorithm is near-optimal.
CS Dept TR Overview