1984/04/01 by Alain Fournier, Delfin Y. Montuno · 5 citations
Computer Science · #Computational Geometry and Mesh Generation #Computer Graphics and Visualization Techniques #Interactive and Immersive Displays #Citation #Simple (philosophy) #Library science #Computer science
paper · pdf · doi:10.1145/357337.357341
openalex publication_date 1984/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
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.