Abstract:
The finite element method is popular in scientific simulation and computer animation as a way to model physical phenomena, and Delaunay triangulations are popular as geometric models of object and domains to be simulated. An ambitious goal is to simulate objects using moving meshes that track the shape of an object undergoing large deformations. The least understood part of this is what I call the "Delaunay repair problem": suppose the vertices of a Delaunay mesh have moved in response to physical forces, and the mesh is no longer Delaunay. Can we recover the Delaunay triangulation of the new vertex configuration faster than reconstructing the triangulation from scratch?

In two dimensions, the answer is yes. In 1977, Charles Lawson showed that any planar triangulation of a vertex set can be transformed into the Delaunay triangulation of the same vertices by a sequence of edge flips. The edge flips can be chosen by a simple hill-climbing algorithm. In three or more dimensions, the notion of an edge flip generalizes to "bistellar flips," and the flip algorithm also generalizes, but the results do not. In practice, three-dimensional flipping gets stuck easily in local optima that are not Delaunay. In five-dimensional space, some triangulations cannot be transformed to Delaunay by any sequence of flips.

Thus I introduce star splaying, an algorithm that transforms any triangulation of any dimensionality into a Delaunay triangulation, and does so in a manner that is fast if few changes are needed. Star splaying has two main ideas.First, a triangulation is represented as a collection of "stars"--a star is the local neighborhood of each vertex. Second, the stars of two different vertices are not required to agree. Because star splaying permits temporary inconsistencies between stars, it can get past local optima that incapacitate
the flip algorithm.