DocumentCode
3175062
Title
Covering polygons is hard
Author
Culberson, Joseph C. ; Reckhow, Robert A.
Author_Institution
Dept. of Comput. Sci., Alberta Univ., Edmonton, Alta., Canada
fYear
1988
fDate
24-26 Oct 1988
Firstpage
601
Lastpage
611
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1988., 29th Annual Symposium on
Conference_Location
White Plains, NY
Print_ISBN
0-8186-0877-3
Type
conf
DOI
10.1109/SFCS.1988.21976
Filename
21976
Link To Document