Covering Polygons is Hard (Preliminary Abstract)

Joseph C. Culberson and Robert A. Reckhow

29th Annual Symposium on Foundations of Computer Science Vol. 21:601-611, 1988.

Abstract

We show 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.
We note that these results hold even if the polygons are required to be in general position.

joe@cs.ualberta.ca