Hay un algoritmo para triangular un polígono en tiempo lineal debido a Chazelle (1991), pero AFAIK no hay implementaciones estándar de su algoritmo en las bibliotecas de software matemático general. ¿Alguien sabe de una implementación tal que no puedo encontrar buscando en Google?Implementación del algoritmo de triangulación Chazelle
Ver este answer to "Powerful Algorithms too complex to implement":
Según Skienna (autor de El Manual de Diseño de Algoritmos), "[la] algoritmo es bastante inútil para poner en práctica."
He buscado una implementación antes, pero no he podido encontrar una. Creo que es seguro asumir que nadie lo ha implementado debido a su complejidad, y creo que también tiene un factor de constancia bastante grande, por lo que no funcionaría bien con los algoritmos O(n lg n) que tienen factores constantes más pequeños.