Benoît Hudson

Dynamic Mesh Refinement Degree Type: Ph.D. in Computer Science
Advisor(s): Gary L. Miller
Graduated: December 2007

Abstract:

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 sparse-meshing.com.

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.

Thesis Committee:
Gary L. Miller (Chair)
Anupam Gupta
Daniel D.K. Sleator
Umut A. Acar (Toyota Technological Institute at Chicago)
Jonathan R. Shewchuk (University of California, Berkeley)

Peter Lee, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Computational geometry, scientific computing, mesh refinement, dynamic algorithms