Covering a polygon (which may contain holes) with star polygons is NP-hard [REF].
Covering a general (non-rectilinear) polygon with star polygons is NP-hard even when the target polygon is hole-free [REF].