MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Kumar, V. S. Anil
Ramesh, Hariharan
dblp
dblp
Editor(s):
BibTeX cite key*:
Kumar1999a
Title, Booktitle
Title*:
Covering Rectilinear Polygons with Axis-Parallel Rectangles
Booktitle*:
Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC-99)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Atlanta, USA
Language:
English
Event Date*
(no longer used):
May 1-4, 1999
Organization:
Association of Computing Machinery(ACM)
Event Start Date:
19 June 2021
Event End Date:
19 June 2021
Publisher
Name*:
ACM
URL:
Address*:
New York, USA
Type:
Extended Abstract
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
May
Pages:
445-454
Year*:
1999
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We give an $O(\sqrt{\log n})$ factor approximation
algorithm for covering a rectilinear polygon with holes using
axis-parallel rectangles.
This is the first polynomial time
approximation algorithm for this problem with
a $o(\log n)$ approximation factor.
Keywords:
Computational Geometry, Approximation Algorithms, Polygon Covering
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Kumar1999a,
AUTHOR = {Kumar, V. S. Anil and Ramesh, Hariharan},
TITLE = {Covering Rectilinear Polygons with Axis-Parallel Rectangles},
BOOKTITLE = {Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC-99)},
PUBLISHER = {ACM},
YEAR = {1999},
TYPE = {Extended Abstract},
ORGANIZATION = {Association of Computing Machinery(ACM)},
PAGES = {445--454},
ADDRESS = {Atlanta, USA},
MONTH = {May},
}


Entry last modified by Uwe Brahm, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
V.S.Anil Kumar
Created
03/21/2000 10:36:22 AM
Revisions
7.
6.
5.
4.
3.
Editor(s)
Uwe Brahm
Anja Becker
Anja Becker
Uwe Brahm
Uwe Brahm
Edit Dates
04/04/2001 07:45:21 PM
07.04.2000 10:04:07
07.04.2000 09:47:36
04.04.2000 11:57:31
04.04.2000 11:57:05