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.