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.