McGill University - School of Computer Science

Algorithms Seminar Summer 2001

Everybody is welcome!

DATE: Thursday, July 12th
TIME: 4:00 PM - 5:00 PM
PLACE: McConnell 320
TITLE: Nice Point Sets Can Have Nasty Delaunay Triangulations (But Not Too Nasty)
SPEAKER: Jeff Erickson, University of Illinois at Urbana-Champaign

e consider the complexity of Delaunay triangulations of sets of points with certain practical geometric constraints. The spread of a set of points is the ratio between the longest and shortest pairwise distances. We show that the Delaunay triangulation of n points in 3-space with spread D has complexity Omega(min{D^3, nD, n^2}) and O(min{D^3, n^2}) in the worst case. For the case D=sqrt{n}, our lower bound construction consists of a grid-like sample of a right circular cylinder with constant height and radius. The upper bound proof relies crucially on the conformal invariance of Delaunay triangulations and the existence of a consistent depth order of their edges from any viewpoint. We also construct a family of smooth connected surfaces such that the Delaunay triangulation of any good point sample has near-quadratic complexity. Most of these results were presented at the 17th ACM Symposium on Computational Geometry. A full version of that paper can be downloaded from here .

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at Algorithms Seminar organization.