IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Sun, 26 Oct 2014 08:41:06

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.

Goto (at Linköping University): CS Dept TR Overview