Close approximations of minimum rectangular coverings
Levcopoulos, Christos LU
and Gudmundsson, Joachim
(1996)
1180.
p.135-146
- 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 doubly-exponential known before). (Less)
Please use this url to cite or link to this publication:
https://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
- host publication
- 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/3-540-62034-6_44
- language
- English
- LU publication?
- yes
- id
- 36a5ca6d-8ce2-4266-abff-359ad5b5a16d (old id 526585)
- date added to LUP
- 2016-04-04 10:31:38
- date last changed
- 2022-01-29 20:26:10
@inproceedings{36a5ca6d-8ce2-4266-abff-359ad5b5a16d,
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 doubly-exponential 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 = {{135--146}},
publisher = {{Springer}},
title = {{Close approximations of minimum rectangular coverings}},
url = {{https://lup.lub.lu.se/search/files/5559741/623756.ps}},
doi = {{10.1007/3-540-62034-6_44}},
volume = {{1180}},
year = {{1996}},
}