SPEAKER: Benoit Hudson

TIME: Wednesday 12-1pm, February 7, 2007

PLACE: NSH 1507

TITLE: Three Recent Mesh Refinement Results

ABSTRACT:
Mesh refinement is the first step in running a finite element simulation:
we take an input geometry (points, segments, polygons, ...) and output a
mesh of triangles and tetrahedra.

I'll report on three exciting new mesh refinement results our group have
come up with in the past year.  First, for the benefit of those who didn't
see Todd's talk last semester, I'll reiterate (without proof) our
optimal-time algorithm for mesh refinement [1].  Next, I'll show how to
work-efficiently parallelize our algorithm to within a log factor of
optimal depth [2].  Finally, I'll show how to dynamically maintain a mesh
as we add or remove points to/from it, in optimal time [3].  There were no
known fast algorithms for any of these problems before except in two
dimensions.

Our work opens up a vast number of open problems, both geometric and
algorithmic; I'll make sure to leave some for the audience to ponder.

References:
[1] Sparse Voronoi Refinement. Benoît Hudson, Gary Miller, and Todd Phillips.
    15th International Meshing Roundtable, 2006.
    http://www.cs.cmu.edu/~bhudson/papers/hudson06sparse.pdf
[2] Sparse Parallel Delaunay Mesh Refinement. Benoît Hudson, Gary Miller, and
    Todd Phillips. In submission. 2007.
    http://www.cs.cmu.edu/~bhudson/papers/hudson07sparse.pdf
[3] Dynamic quad-tree mesh refinement. Benoît Hudson and Umut A. Acar. 
    In submission. 2007.
    http://www.cs.cmu.edu/~bhudson/papers/hudson07dynamic.pdf