Computer Science Department
School of Computer Science, Carnegie Mellon University
Dynamic Mesh Refinement
Mesh refinement is the problem to produce a triangulation (typically Delaunay) of an input set of points augmented by Steiner points, such that every triangle or tetrahedron has good quality (no small angles). The requirement arises from the applications: in scientific computing and in graphics, meshes are often used to discretely represent the value of a function over space. In addition to the quality requirement, the user often has input segments or polygons (generally, a piecewise linear complex) they would like see retained in the mesh; the mesh must respect these constraints. Finally, the mesh should be size-conforming: the size of mesh elements should be related to a particular sizing function based on the distance between input features.
The static meshing problem is increasingly well-understood: one can
download software with provable guarantees that on reasonable input, the
meshes will have good quality, will respect the input, and will be
size-conforming; more recently, these algorithms have started to come with
optimal runtimes of O(n log (L/s) + m), where L/s is the
spread of the input. As a first result, I present experimental results of
the first time-optimal code, available online at
Increasingly, static meshing is insufficient: users want to modify the mesh over time. Throwing away the old mesh and remeshing from scratch is a common approach, but that suffers from slow runtime, and from reinterpolation error because the old and new meshes may be almost unrelated. Mesh stability analyzes the correspondence between meshes for two inputs. The main theoretical result of this thesis is an algorithm that has provable bounds on stability: upon inserting or removing a feature that in the final mesh is represented using k points, the mesh only modifies O(k log (L/s)) mesh simplices.
Finally, stability can be exploited to produce an efficient dynamic algorithm. Under the self-adjusting computation framework, with a small amount of additional effort, I show that my algorithm can be dynamized to run in O(k log (L/s)) time per update, using O(n log (L/s) + m) space.