de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Covering Rectilinear Polygons with Axis-Parallel Rectangles

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44863

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44586

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

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
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.