@techreport{R-86-03,
TITLE = {A fast Heuristic for Covering Polygons by Rectangles},
AUTHOR = {Christos Levcopoulos},
YEAR = {1986},
NUMBER = {R-86-03},
INSTITUTION = ida,
ADDRESS = idaaddr,
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-86-03+abstr},
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.},
IDANR = {LiTH-IDA-R-86-03},
NOTE = {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}