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

IDA Technical Reports: abstract

Generated: Fri, 18 Apr 2014 05:01:43

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
<webmaster@ida.liu.se>