Covering polygons is hard. (English) Zbl 0811.68089
Summary: 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 result hold even if the polygons are required to be in general position.
MSC:
68Q25 | Analysis of algorithms and problem complexity |
68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |