Advanced

Close Approximations of Minimum Rectangular Coverings

Levcopoulos, Christos LU and Gudmundsson, Joachim (1999) In Journal of Combinatorial Optimization 3(4). p.437-452
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:
author
organization
publishing date
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
1382-6905
DOI
10.1023/A:1009879504783
language
English
LU publication?
yes
id
f85f34db-fd8f-480f-9b36-cc30fcb7b8e0 (old id 114273)
date added to LUP
2007-07-23 13:52:01
date last changed
2017-01-01 07:15:19
@article{f85f34db-fd8f-480f-9b36-cc30fcb7b8e0,
  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},
  issn         = {1382-6905},
  keyword      = {computational geometry,covering polygons,approximation algorithms},
  language     = {eng},
  number       = {4},
  pages        = {437--452},
  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},
}