Generating Well-Shaped Delaunay Meshes

Abstract

A mesh is cell-complex that decomposes a spatial domain for numerical simulation. Delaunay triangulations have many desirable properties for mesh generation. While there are several efficient methods for well-shaped 2D mesh generation, the generation of Delaunay meshes of well-shaped tetrahedra in 3D is considerably more difficult and has been an outstanding open problem for many years. Most notably, slivers are notoriously common in three dimensional Delaunay meshes, where a sliver is a tetrahedron that has no short edge and whose four vertices lie closely to a great circle of its circum-sphere.

In this talk, I will survey the algorithmic and geometric techniques using weighted Delaunay triangulations and perturbations, that are recently developed for sliver removal. In particular, I will present the first Delaunay refinement algorithm, developed by Li and Teng, that always generates sliver free well-shaped unstructured meshes in three dimensions. The main ingredient of this algorithm is a novel refinement technique which systematically forbids the formation of slivers.

This talk contains collaborative works with Shang-Hua Teng, Siu-Wing Cheng, Tamal Dey, Herbert Edelsbrunner, Micheal Facello, Alper Ungor, Gary Miller, Dafna Talmor, and Noel Walkington.