de.mpg.escidoc.pubman.appbase.FacesBean
English

# 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.