Close Approximations of Minimum Rectangular Coverings
(1999) In Journal of Combinatorial Optimization 3(4). p.437452 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/114273
 author
 Levcopoulos, Christos ^{LU} and Gudmundsson, Joachim
 organization
 publishing date
 1999
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 computational geometry, covering polygons, approximation algorithms
 in
 Journal of Combinatorial Optimization
 volume
 3
 issue
 4
 pages
 437  452
 publisher
 Kluwer
 external identifiers

 scopus:0037749514
 ISSN
 13826905
 DOI
 10.1023/A:1009879504783
 language
 English
 LU publication?
 yes
 id
 f85f34dbfd8f480f9b36cc30fcb7b8e0 (old id 114273)
 date added to LUP
 20070723 13:52:01
 date last changed
 20180107 09:32:45
@article{f85f34dbfd8f480f9b36cc30fcb7b8e0, 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}, issn = {13826905}, keyword = {computational geometry,covering polygons,approximation algorithms}, language = {eng}, number = {4}, pages = {437452}, publisher = {Kluwer}, series = {Journal of Combinatorial Optimization}, title = {Close Approximations of Minimum Rectangular Coverings}, url = {http://dx.doi.org/10.1023/A:1009879504783}, volume = {3}, year = {1999}, }