FOCS Conference 1988 Conference Paper
Covering Polygons Is Hard (Preliminary Abstract)
- Joseph C. Culberson
- Robert A. Reckhow
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. >