ylfink@water.waterloo.edu (ylfink) (05/12/88)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
THEORY/GRAPHICS SEMINAR .sp .ta 2i .br
- Friday, May 20, 1988
Mr. Michael B. Dillencourt,
will speak on ``Graph Theoretic Properties Involving Delaunay Triangulations''.
TIME: 3:30 PM
ROOM: DC 1302
ABSTRACT
The Delaunay triangulation is one the fundamental
structures of computational geometry. This talk will
discuss some recent results concerning the graph-
theoretical structure of Delaunay triangulations and
related problems.
Hamiltonian cycles through Delaunay triangulations are
useful for solving certain problems arising in computer
graphics and pattern recognition. It will be shown
that while Delaunay triangulations do not always have
Hamiltonian cycles, they do have some related graph-
theoretic properties. Similar results will be shown
for the closely related family of inscribable graphs
(that is, graphs that can be realized as the vertices
and edges of a polytope inscribed in a sphere). The
problem of determining whether a triangulation can be
realized as a (combinatorially equivalent) Delaunay
triangulation will also be considered. Several open
conjectures, and some supporting empirical evidence,
will be presented.