Covering Polygons is Hard.
Joseph C. Culberson and Robert A. Reckhow
Journal of Algorithms vol 17, 2-44, 1994.
Abstract
We show the following for polygons without holes:
- covering the interior or boundary of
an arbitrary polygon with convex polygons is NP-hard;
- covering the vertices of an arbitrary polygon with convex polygons is
NP-complete;
- covering the interior or boundary of an orthogonal polygon with rectangles
is NP-complete.
We note that these results hold even if the polygons are required to be in
general position.
Postscript of paper (without some figures)
Additional figures
joe@cs.ualberta.ca