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:
- covering an arbitrary polygon with convex polygons
- covering the boundary of an arbitrary polygon with convex polygons
- covering an orthogonal polygon with rectangles, and
- 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