Efficient triangulation of simple polygons

This paper considers the topic of efficiently traingulating a simple polygon with emphasis on practical and easy-to-implement algorithms. It also describes a new adaptive algorithm for triangulating a simple n-sided polygon. The algorithm runs in time O(n(1+t_o)) with t₀<n. The quantity t₀ measures the shape-complexity of the triangulation delivered by the algorithm. More precisely t₀ is the number of obtained triangles contained in the triangulation that share zero edges with the input polygon and is, furthermore, related to the shape-complexity of the input polygon. Although the worst-case complexity of the algorithm is O(n²), for several classes of polygons it runs in linear time. The practical advantages of the algorithm are that it is simple and does not require sorting or the use of balanced tree structures. On the theoretical side, it is of interest because it is the first polygon triangulation algorithm where the computational complexity is a function of the output complexity. As a side benefit, we introduce a new measure of the complexity of a polygon triangulation that should find application in other contexts as well.