A Review of Two Simple Polygon Triangulation Algorithms

This paper describes two approaches to triangulate a simple polygon. Emphasis is on practical and easy to implement algorithms, especially the first algorithm is straightforward and intuitive but, however, quite efficient. Further, it does not require the sorting or the use of balanced tree structures. Its worst running time complexity is O(n 2 ), but for special classes of polygons it runs in linear time. The second approach requires some more sophisticated concepts of computational geometry but yields a better worst running time complexity of O(n log n). Both algorithms do not introduce new vertices and triangulate in a greedy fashion, that is they never remove edges once inserted. Further, they are designed to find an arbitrary triangulation and they do not optimize the result in any way. Keywords: computational geometry, polygon, triangulation, computational complexity, monotone polygon, trapezoidation 1 Introduction The problem of triangulating a polygon can be stated as: "giv..