Covering Rectilinear Polygons with Axis-Parallel Rectangles

Kumar, V. S. Anil; Hariharan, Ramesh

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

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 Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

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: https://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.