[ont.events] The Difficulty of Covering Polygons.

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.