Триангуляция плоского многоугольника

15

Существуют ли сейчас более простые алгоритмы / доказательства триангуляции плоского многоугольника за линейное время? Что является хорошим ресурсом о состоянии этой знаменитой проблемы?

reference-request cg.comp-geom Гил Калай
источник

Ответы:

13

Пока что единственное улучшение в Джазернауте Шазель - это рандомизированный алгоритм линейного времени 2001 года Амато, Гудрича и Рамоса . Алгоритм Шазеля до сих пор является единственным известным детерминированным алгоритмом триангуляции за O (n) -время.

Jeffε
источник