Speaker: Benoit Hudson Time: Wednesday 12-1pm Place: NSH 1507 Title: Time-Optimal Incremental Delaunay Refinement Abstract: Delaunay mesh refinement is widely used in scientific computing, because in practice it is fast. However, for about 10 years there were no time bounds on the technique faster than O(n^2). Indeed, many known algorithms exhibited quadratic-time behaviour in some bad cases that would occasionally be encountered in the wild. I will present the basic technique from Jim Ruppert's 1995 paper, followed by the main ideas from Gary Miller SODA'04 paper that proves near-optimal time bounds. Time permitting, I will also touch on some more recent work Todd Phillips, Gary and I have done to extend the result to three (or more) dimensions. This talk is in partial fulfillment of the speaking requirement.