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:
  1. covering the interior or boundary of an arbitrary polygon with convex polygons is NP-hard;
  2. covering the vertices of an arbitrary polygon with convex polygons is NP-complete;
  3. 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