Covering polygons is hard
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 601-611
- https://doi.org/10.1109/sfcs.1988.21976
Abstract
It is shown that the following minimum cover problems are NP-hard, even for polygons without holes: (1) covering an arbitrary polygon with convex polygons; (2) covering the boundary of an arbitrary polygon with convex polygons; (3) covering an orthogonal polygon with rectangles; and (4) covering the boundary of an orthogonal polygon with rectangles. It is noted that these results hold even if the polygons are required to be in general position.Keywords
This publication has 9 references indexed in Scilit:
- Orthogonally convex coverings of orthogonal polygons without holesJournal of Computer and System Sciences, 1989
- Covering orthogonal polygons with star polygons: the perfect graph approachPublished by Association for Computing Machinery (ACM) ,1988
- Minimally covering a horizontally convex orthogonal polygonPublished by Association for Computing Machinery (ACM) ,1986
- Decomposing a Polygon into Simpler ComponentsSIAM Journal on Computing, 1985
- An algorithm for constructing regions with rectanglesPublished by Association for Computing Machinery (ACM) ,1984
- Some NP-hard polygon decomposition problemsIEEE Transactions on Information Theory, 1983
- The power of non-rectilinear holesPublished by Springer Nature ,1982
- Covering Regions by RectanglesSIAM Journal on Algebraic Discrete Methods, 1981
- Decomposing a polygon into its convex partsPublished by Association for Computing Machinery (ACM) ,1979