Lingas, A. (1985). A Linear-Time Heuristic for Minimum Weight Triangulation of Convex Polygons. Technical Report LiTH-IDA-R-85-12, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc. of the Allerton Conference on Communication, Control, and Computing, Urbana, Illinois, October, 1985. (bibtex),
Abstract: A simple heuristic for minimum weight triangulation of convex polygons is presented. For a convex polygon with n vertices, the heuristic runs in time O(n), and produces a solution within an O(logn) factor from the minimum. Generalizations of the heuristic to include non-convex polygons are also derived.
CS Dept TR Overview