A linear-time near-optimum-length triangulation algorithm for convex polygons

摘要

This paper shows how to compute a short triangulation for a convex polygon in O(n) time, where n is the number of sides of the input polygon. The resulting triangulation is guaranteed to be of a total length that is only a constant factor of the shortest possible.