Trianguler un polygone plan

15

Existe-t-il désormais des algorithmes / preuves plus simples pour trianguler un polygone plan en temps linéaire? Quelle est une bonne ressource sur l'état de l'art de ce fameux problème?

reference-request cg.comp-geom Gil Kalai
la source

Réponses:

13

Jusqu'à présent, la seule amélioration apportée au mastodonte de Chazelle est l'algorithme de temps linéaire randomisé de 2001 par Amato, Goodrich et Ramos . L'algorithme de Chazelle est toujours le seul algorithme déterministe de triangulation à temps O (n) connu.

Jeffε
la source