SPEAKER: Todd Phillips

TIME: Wednesday 12-1pm, October 25, 2006

PLACE: NSH 1507

TITLE: Runtime-Efficient Meshing Algorithms

ABSTRACT:
I will overview the meshing problem in three and higher dimensions,
presenting various state of the art algorithmic guarantees on the output.
I will present a simple new meshing algorithm, "Sparse Voronoi Refinement"
(SVR), that provides near-optimal worst case runtime along with output
guarantees. We will explore how packing and structural lemmas lead to a
concise, elegant proof of the runtime guarantees. We will discuss more
complex extensions of SVR as well as SVR's implications for
future meshing research. This is joint work with Gary Miller and Benoit
Hudson.