English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Covering Rectilinear Polygons with Axis-Parallel Rectangles

MPS-Authors
/persons/resource/persons44863

Kumar,  V. S. Anil
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44586

Hariharan,  Ramesh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Kumar, V. S. A., & Hariharan, R. (1999). Covering Rectilinear Polygons with Axis-Parallel Rectangles. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC-99) (pp. 445-454). New York, USA: ACM.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-35B4-7
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.