wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (04/29/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DNUMERICAL ANALYSIS SEMINAR
-Friday, May 5, 1989
Dr. Barry Joe, Dept. of Computing Science, University
of Alberta, will speak on "Construction of 3-D
Triangulations Using Local Transformations."
TIME: 10:30-12:00
ROOM: DC 1302
ABSTRACT
A 2-D (Delaunay) triangulation can be constructed using
a local transformation procedure which swaps the
diagonal edge of 2 adjacent triangles forming a
strictly convex quadrilateral. An analogous local
transformation procedure can be used to construct a 3-D
triangulation, i.e. a connection of n 3-D points into
-
non-overlapping tetrahedrons which fill the convex hull
of the points. This 3-D procedure swaps the interior
faces in 2 or 3 adjacent tetrahedrons forming a convex
hexahedron.
In this talk, we present a new algorithm for
constructing a 3-D Delaunay triangulation using local
transformations. This algorithm has a worst case time
2
complexity of O(n ), which is worst case optimal. For
- -
sets of random points, the expected and empirical time
4/3
-
complexity of this algorithm is O(n ). We also
- -
present a related algorithm in which the local
transformations are not explicitly performed, and
discuss pseudo-locally-optimal non-Delaunay
triangulations and triangulations based on the max-min
solid angle criterion.