Triangulating Simple Polygons and Equivalent Problems

Abstract

It' has long been known that the complexity of triangulation of simple polygons having an upper bound of 0 (n log n) but a lower bound higher than ~(n) has not been proved yet. We propose here an easily implemented route to the triangulation of simple polygons through the trapezoidization of simple polygons, which is currently done in O(n log n). Then the trapezoidized polygons are triangulated in O(n) time. Both of those steps can be performed on polygons with holes with the same complexity.