vrsyrotiuk@water.waterloo.edu (Violet Syrotiuk) (03/14/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DATA STRUCTURES SEMINAR
- Monday, March 20, 1989
Dr. Hazel Everett, of the Department of Computer
Science at the University of Toronto, will speak on
``Recognizing the Visibility Graphs of Spiral
Polygons''.
TIME: 3:30 PM
ROOM: DC 1304
ABSTRACT
Given a simple polygon its visibility graph is defined
as follows: the vertices of the graph correspond to the
vertices of the polygon and two vertices in the graph
are adjacent if the line segment between them lies
entirely within the polygon. Visibility graphs are
important in the solutions to such problems in robot
motion planning as finding shortest paths in polygonal
scenes and have been the focus of much research effort
in recent years. The recognition problem for
visibility graphs is given a graph determine whether it
is the visibility graph of a simple polygon. Little is
known about the complexity of this problem. In this
talk I present a linear time recognition algorithm for
the visibility graphs of spiral polygons. These graphs
are shown to be interval graphs and this property is
used extensively in the recognition algorithm.
--
Violet R. Syrotiuk | vrsyrotiuk@water.uucp
Computer Science Dept. | watmath!water!vrsyrotiuk
University of Waterloo | vrsyrotiuk@water.uwaterloo.ca
Waterloo, ON N2L 3G1 | vrsyrotiuk@water.waterloo.edu (or .cdn)