Newsgroups: ut.theory
Path: utzoo!utgpu!jarvis.csri.toronto.edu!neat.ai.toronto.edu!bmkapron
From: bmkapron@theory.utoronto.ca (Bruce Kapron)
Subject: Meeting of Student Seminar
Message-ID: <89Jan27.150645est.38064@neat.ai.toronto.edu>
Organization: Department of Computer Science, University of Toronto
Distribution: ut
Date: Fri, 27 Jan 89 15:06:45 EST

Time: Tuesday, January 31 1989. 3pm EST.

Location: GB420

Speaker: Hazel Everett


Recognizing the Visibility Graphs of Spiral Polygons

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. This constitutes
the first non-trivial recognition algorithm for the visibility graphs
of a restricted class of polygons.