Задача о триангуляции многоугольника — классическая задача комбинаторной и вычислительной геометрии, состоящая в нахождении триангуляции многоугольника без дополнительных вершин.

Формулировка

Задача состоит в нахождении оптимального алгоритма триангуляции n-угольника без дополнительных вершин.

Эта задача может быть решена за линейное время, то есть задача имеет сложность ${\displaystyle O(n)}$.

Доказательство существования такой триангуляции не представляет сложности. Более того, эта задача всегда имеет решение для многоугольников с дырками, то есть областей плоскости, ограниченных несколькими замкнутыми ломаными.

История

Долгое время был открытым вопрос, можно ли найти триангуляцию n-угольника за время, меньше, чем ${\displaystyle O(n\log n)}$.^[1] Затем Ван Вик (1988) обнаружил алгоритм, требующий время ${\displaystyle O(n\log \log n)}$,^[2] позже упрощённый Киркпатриком и Клаве.^[3] Затем последовало несколько алгоритмов со сложностью ${\displaystyle O(n\log ^{*}n)}$, не отличимых на практике от линейного времени.^[4][5][6]

В 1991 году Бернард Чазелле доказал, что любой простой многоугольник может быть триангулирован в линейное время, хотя предложенный им алгоритм оказался очень сложным.^[7] Более простой вероятностный алгоритм с линейным ожидаемым временем также известен.^[8][9]

Алгоритмы

Отрезание ушей

Двойственный граф триангуляции без дополнительных вершин у простого многоугольника всегда является деревом. Отсюда в частности следует, что любой простой n-угольник с n > 3 имеет по меньшей мере два уха, то есть два треугольника, две стороны каждого из которых являются сторонами многоугольника, а третья полностью внутри него.^[10]

Один из способов триангуляции состоит в нахождении такого уха и отрезании его от многоугольника. После этого ту же операцию повторно применяют к оставшемуся многоугольнику до тех пор, пока не останется один треугольник.

Этот способ работает только для многоугольников без дырок. Он прост в реализации, но работает медленнее, чем некоторые другие алгоритмы. Реализация, которая хранит отдельные списки выпуклых и вогнутых вершин, работает за время ${\displaystyle O(n^{2})}$.

Эффективный алгоритм для отрезания ушей был предложен Хоссамом Эль-Гинди, Хэзелом Эвереттом и Годфридом Туссеном.^[11]

Через монотонные многоугольники

Многоугольник называется монотонным, если его граничная ломаная имеет не более двух точек пересечения с прямой, перпендикулярной данной.

Монотонный многоугольник может быть триангулирован за линейное время с помощью алгоритма А. Фурнье и Д. Ю. Монтуно^[12] или алгоритма Годфрид Туссен.^[13]

Произвольный многоугольник может быть подразбит на монотонные. Алгоритм триангуляции простого многоугольника, построенный на этой идее, работает за время ${\displaystyle O(n\log n)}$.

Вариации и обобщения

• Триангуляция многогранника без дополнительных вершин существует не всегда. Пример можно найти среди невыпуклых октаэдров, см. рисунок.
• Выпуклый многоугольник является тривиальной задачей триангуляции. Она решается в линейное время. Можно провести диагонали из одной вершины ко всем другим вершинам.
  • Общее число способов триангулировать выпуклый n-угольник диагоналями равно числу Каталана

    ${\displaystyle {\tfrac {n\cdot (n+1)\cdots (2n-4)}{(n-2)!}}.}$

Последнее было доказано Эйлером.^[14]

Ссылки