eas@utcsrgv.UUCP (Ann Struthers) (01/11/85)
Subject: Abstract/Theoretical Aspects Seminar
Newsgroups: ont.events
Distribution: ont
*** REPLACE THIS LINE WITH YOUR MESSAGE ***
THEORETICAL ASPECTS SEMINAR
Thursday, January 17, 1984
4:00 P.M. Sandford Fleming Building 1101
Ms. Anna Lubiw
Ph.D. candidate in the Department of Computer Science
University of Toronto
"Decomposing a Polygonal Region into Convex Quadrilaterals"
A polygonal region is formed by cutting holes bounded by polygons out
of the region bounded by a polygon. Decomposing a polygonal region
means partitioning the region into simpler polygons by adding chords,
which are line segments inside the region joining pairs of vertices.
Khan, Klawe & Kleitman proved (as a step towards positioning watchmen
in conventional art galleries) that every rectilinear region can be
decomposed into convex quadrilaterals. A rectilinear region is a poly-
gonal region whose edges are all parallel to the x or y axis. I look
at larger classes of polygonal regions which are CQ hereditary - i.e.
every region in the class contains a convex quadrilateral whose removal
leaves polygonal regions in the class. I obtain an O(nlogn) algorithm
to decompose n-vertex rectilinear regions into convex quadrilaterals.