Многоугольная триангуляция

• Определение и применение триангуляции

  • Триангуляция – разбиение многоугольника на треугольники с непересекающимися внутренностями. 
  • Триангуляции являются частными случаями плоских прямолинейных графов. 
  • Без дополнительных вершин триангуляции образуют максимальные внешние плоские графики. 

• Алгоритмы триангуляции

  • Существуют различные алгоритмы для триангуляции, включая веерную триангуляцию и алгоритм обрезания ушей. 
  • Монотонные многоугольники могут быть триангулированы за линейное время. 
  • Немонотонные многоугольники могут быть разбиты на монотонные подполигоны и триангулированы за O(n log n) времени. 

• Двойной граф триангуляции

  • Двойной граф триангуляции – это дерево с максимальной степенью 3, связанное с триангуляцией. 

• Вычислительная сложность

  • До 1988 года не было известно, как триангулировать многоугольник быстрее, чем за O(n log n) времени. 
  • В 1988 году был открыт алгоритм триангуляции за O(n log log n) времени. 
  • Существуют улучшенные методы с сложностью O(n log* n). 
  • Линейное время триангуляции возможно, но сложно. 

• Связанные объекты и проблемы

  • Триангуляция является частным случаем триангуляции и разбиения на полигоны. 
  • Существуют задачи триангуляции с минимальным весом, покрытия треугольника и разбиения на многоугольники. 

• Рекомендации

  • Ссылки на внешние ресурсы и демонстрации алгоритмов предоставлены в конце статьи.