Title :
Covering polygons is hard
Author :
Culberson, Joseph C. ; Reckhow, Robert A.
Author_Institution :
Dept. of Comput. Sci., Alberta Univ., Edmonton, Alta., Canada
Abstract :
It is shown 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. It is noted that these results hold even if the polygons are required to be in general position
Keywords :
computational complexity; computational geometry; NP-hard; arbitrary polygon; boundary; convex polygons; covering problems; minimum cover problems; orthogonal polygon; rectangles; Partitioning algorithms; Polynomials; Spirals; Structural beams;
Conference_Titel :
Foundations of Computer Science, 1988., 29th Annual Symposium on
Conference_Location :
White Plains, NY
Print_ISBN :
0-8186-0877-3
DOI :
10.1109/SFCS.1988.21976
