A Competitive Algorithm for No-Large-Angle Triangulation

Presented at Theory Lunch, Carnegie Mellon University, May 2, 2007

In this talk, I will present Overlay Stitch Meshing, a novel new algorithm that simultaneously solves two different problems in the field of triangulating planar straight-line graphs in the plane for scientific computing applications:
It is the first Delaunay Refinement-type triangulation algorithm that terminates with a full complement of guarantees even on degenerate inputs and with no dependence on the size of the smallest input angle.
It is the first algorithm that gives a log competitive output size for the problem of no-large-angle triangulation with Steiner points.
The workings of the algorithm are very easy to state and understand. The brunt of the talk will focus on new analytic techniques that allow us to prove strong guarantees.