ICS Theory Group

ICS 269, Spring 1997: Theory Seminar

21 November 1997:
Approximate Minimum Weight Triangulation of Convex Polygons
Brad Hutchings, ICS, UC Irvine

Today in Theory Group, I'll be presenting a paper by Levcopoulos and Krznaric that describes their heuristic for finding a 1+e approximation of the minimum weight triangulation of convex polygons in O(n) time. This result is theoretically quite practical because it beats the best known exact algorithm's time of O(n3) while not yielding a terribly bad triangulation. Their result can be applied to speed up many heuristics for triangulation of general point sets.