Задача о триангуляции многоугольника

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

Триангуляция многоугольника без дополнительных вершин.

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

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

Задача состоит в нахождении оптимального алгоритма триангуляции 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)}$ (где ${\displaystyle \log ^{*}n}$ — итерированный логарифм), не отличимых на практике от линейного времени.^[4][5][6]

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

Алгоритмы

Многоугольник и его ухо

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

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

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

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

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

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

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

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

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

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

Многогранник Шёнхардта не допускает триангуляции без дополнительных вершин

• Триангуляция многогранника без дополнительных вершин существует не всегда. Примером является Многогранник Шёнхардта, см. рисунок.

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

• Триангуляция выпуклого многоугольника является тривиальной задачей. Она решается в линейное время путём проведения всевозможных диагоналей из одной вершины к остальным.
  • Общее число способов триангулировать выпуклый ${\displaystyle n}$-угольник диагоналями равно числу Каталана под номером ${\displaystyle (n-2)}$, что было доказано Эйлером.^[14]

См. также

• Теорема о сумме углов многоугольника

• Задача о картинной галерее