September 11, 2007
Benoît Hudson
10:00 AM, 3305 Newell-Simon Hall
Thesis Oral
Title: Dynamic Mesh Refinement
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 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 — in particular, elements should not be too small.
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). As a first result, I present experimental results of the first time-optimal code.
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 analyses 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 the above 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 Miller, Chair
Anupam Gupta
Daniel Sleator
Umut A. Acar, Toyota Technological Institute at Chicago
Jonathan R. Shewchuk, University of California, Berkeley
