Close approximations of minimum rectangular coverings
(1996) In Foundations of software technology and theoretical computer science : 16th Conference / Lecture notes in computer science 1180. p.135146 Abstract
 We consider the problem of covering arbitrary polygons with rectangles. The rectangles must lie entirely within the polygon. (This requires that the interior angles of the polygon are all greater than or equal to 90 degrees.) We want to cover the polygon with as few rectangles as possible. This problem has an application in fabricating masks for integrated circuits.
In this paper we will describe the first polynomial algorithm, guaranteeing an O(log n) approximation factor, provided that the n vertices of the input polygon are given as polynomially bounded integer coordinates. By the same technique we also obtain the first algorithm producing a covering which is within a constant factor of the optimal in exponential time (compared... (More)  We consider the problem of covering arbitrary polygons with rectangles. The rectangles must lie entirely within the polygon. (This requires that the interior angles of the polygon are all greater than or equal to 90 degrees.) We want to cover the polygon with as few rectangles as possible. This problem has an application in fabricating masks for integrated circuits.
In this paper we will describe the first polynomial algorithm, guaranteeing an O(log n) approximation factor, provided that the n vertices of the input polygon are given as polynomially bounded integer coordinates. By the same technique we also obtain the first algorithm producing a covering which is within a constant factor of the optimal in exponential time (compared to the doublyexponential known before). (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/526585
 author
 Levcopoulos, Christos ^{LU} and Gudmundsson, Joachim
 organization
 publishing date
 1996
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 Foundations of software technology and theoretical computer science : 16th Conference / Lecture notes in computer science
 volume
 1180
 pages
 135  146
 publisher
 Springer
 external identifiers

 Scopus:0942271196
 ISBN
 3540620346
 DOI
 10.1007/3540620346_44
 language
 English
 LU publication?
 yes
 id
 36a5ca6d8ce24266abff359ad5b5a16d (old id 526585)
 date added to LUP
 20070921 11:35:17
 date last changed
 20170101 07:58:22
@inproceedings{36a5ca6d8ce24266abff359ad5b5a16d, abstract = {We consider the problem of covering arbitrary polygons with rectangles. The rectangles must lie entirely within the polygon. (This requires that the interior angles of the polygon are all greater than or equal to 90 degrees.) We want to cover the polygon with as few rectangles as possible. This problem has an application in fabricating masks for integrated circuits.<br/><br> In this paper we will describe the first polynomial algorithm, guaranteeing an O(log n) approximation factor, provided that the n vertices of the input polygon are given as polynomially bounded integer coordinates. By the same technique we also obtain the first algorithm producing a covering which is within a constant factor of the optimal in exponential time (compared to the doublyexponential known before).}, author = {Levcopoulos, Christos and Gudmundsson, Joachim}, booktitle = {Foundations of software technology and theoretical computer science : 16th Conference / Lecture notes in computer science}, isbn = {3540620346}, language = {eng}, pages = {135146}, publisher = {Springer}, title = {Close approximations of minimum rectangular coverings}, url = {http://dx.doi.org/10.1007/3540620346_44}, volume = {1180}, year = {1996}, }