Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures (Q1189285)

An \(O(n\log\log n)\) time algorithm for triangulating simple \(n\)-vertex polygons is presented. The rasterized version of the algorithm even consumes \(O(n\log^* n)\) time. Comparing to optimal linear time triangulating algorithms due to \textit{B. Chazelle} [Discrete Comput. Geom 6(5), 485-524 (1991)] the underlying data structures and procedures are quite simple. The algorithm is based on the balanced horizontal visibility partition of a given polygon.