25
Oct
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.
