# 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(n^{3}) while not yielding a terribly bad triangulation.
Their result can be applied to speed up many heuristics for
triangulation of general point sets.