SPEAKER: Don Sheehy.
TIME: Wednesday 12-1pm, May 2, 2007.
PLACE: NSH 1507
TITLE: A Competitive Algorithm for No-Large-Angle Triangulation
ABSTRACT:
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:
1. 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.
2. It is the first algorithm that gives a log n 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.
This talk is in partial fulfillment of the speaking skills requirement.