ylfink@water.waterloo.edu (ylfink) (07/25/88)
DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF WATERLOO SEMINAR ACTIVITIES DATA STRUCTURING SEMINAR - Thursday, July 28, 1988 Professor Joseph C. Culberson, University of Alberta, will speak on ``The Difficulty of Covering Polygons''. TIME: 10:30 AM ROOM: DC 1302 ABSTRACT We show 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. Note that these results hold even if the polygons are required to be in general position.