• numerical methods for simulating physical phenomena including mechanical deformation, heat transfer, and fluid flow;
• graphics (especially radiosity);
• terrain databases and Geographical Information Systems;
• function interpolation; and more.

In this talk, I discuss the design and current state of the art of Delaunay refinement methods. These methods are distinguished from most other mesh generation techniques by their ability to generate meshes whose triangles or tetrahedra satisfy theoretically guaranteed bounds on their shape and size. Yet, unlike provably good quadtree-based methods, they are entirely practical. To address the needs of Carnegie Mellon's Quake project - an interdisciplinary Grand Challenge Application Group whose goal is to simulate earthquake-induced ground motion in the Los Angeles basin - I have produced two general-purpose mesh generators. Triangle and Pyramid are implementations of two- and three-dimensional Delaunay refinement. Triangle has been released to the public, and has thousands of users in research and industrial settings.

I present a new three-dimensional Delaunay refinement algorithm that builds on the pioneering two-dimensional work of L. Paul Chew and Jim Ruppert. My algorithm produces tetrahedral meshes that are nicely graded (in a provable sense) and whose tetrahedra have circumradius-to-shortest edge ratios bounded below 1.63. This theoretical guarantee ensures that all poor quality tetrahedra except slivers (a particular class of poor tetrahedra) are removed. The slivers that remain are easily removed in practice, although there is no theoretical guarantee. In addition to yielding bounds for three-dimensional Delaunay refinement, my analysis techniques have yielded a modification to the existing two-dimensional algorithms that removes the last barrier to their full practicality.

SCS Distinguished Lecture Schedule
SCS Calendar of Events