Русская Википедия:Задача о триангуляции многоугольника
Задача о триангуляции многоугольника — классическая задача комбинаторной и вычислительной геометрии, состоящая в нахождении триангуляции многоугольника без дополнительных вершин.
Доказательство существования такой триангуляции не представляет сложности. Более того, эта задача всегда имеет решение для многоугольников с дырками, то есть областей плоскости, ограниченных несколькими замкнутыми ломаными.
Формулировка
Задача состоит в нахождении оптимального алгоритма триангуляции n-угольника без дополнительных вершин.
Эта задача может быть решена за линейное время, то есть задача имеет сложность <math>O(n)</math>.
История
Долгое время был открытым вопрос, можно ли найти триангуляцию n-угольника за время, меньше, чем <math>O(n \log n)</math>.[1] Затем Ван Вик (1988) обнаружил алгоритм, требующий время <math>O(n \log \log n)</math>,[2] позже упрощённый Киркпатриком и Клаве.[3] Затем последовало несколько алгоритмов со сложностью <math>O(n \log^* n)</math> (где <math>\log^* n</math> — итерированный логарифм), не отличимых на практике от линейного времени.[4][5][6]
В 1991 году Бернард Чазелле доказал, что любой простой многоугольник может быть триангулирован в линейное время, хотя предложенный им алгоритм оказался очень сложным.[7] Также известен более простой вероятностный алгоритм с линейным ожидаемым временем.[8][9]
Алгоритмы
Отрезание ушей
Двойственный граф триангуляции без дополнительных вершин у простого многоугольника всегда является деревом. Отсюда в частности следует, что любой простой n-угольник с n > 3 имеет по меньшей мере два уха, то есть два треугольника, две стороны каждого из которых являются сторонами многоугольника, а третья полностью внутри него.[10]
Один из способов триангуляции состоит в нахождении такого уха и отрезании его от многоугольника. После этого ту же операцию повторно применяют к оставшемуся многоугольнику до тех пор, пока не останется один треугольник.
Этот способ работает только для многоугольников без дырок. Он прост в реализации, но работает медленнее, чем некоторые другие алгоритмы. Реализация, которая хранит отдельные списки выпуклых и вогнутых вершин, работает за время <math>O(n^2)</math>.
Эффективный алгоритм для отрезания ушей был предложен Хоссамом Эль-Гинди, Хэзелом Эвереттом и Годфридом Туссеном.[11]
Через монотонные многоугольники
Многоугольник называется монотонным, если его граничная ломаная имеет не более двух точек пересечения с прямой, перпендикулярной данной.
Монотонный многоугольник может быть триангулирован за линейное время с помощью алгоритма А. Фурнье и Д. Ю. Монтуно[12] или алгоритма Годфрид Туссен.[13]
Произвольный многоугольник может быть подразбит на монотонные. Алгоритм триангуляции простого многоугольника, построенный на этой идее, работает за время <math>O(n\cdot \log n)</math>.
Вариации и обобщения
- Триангуляция многогранника без дополнительных вершин существует не всегда. Примером является Многогранник Шёнхардта, см. рисунок.
- Триангуляция выпуклого многоугольника является тривиальной задачей. Она решается в линейное время путём проведения всевозможных диагоналей из одной вершины к остальным.
- Общее число способов триангулировать выпуклый <math>n</math>-угольник диагоналями равно числу Каталана под номером <math>(n-2)</math>, что было доказано Эйлером.[14]
См. также
Примечания
Ссылки
- Demo as Flash swf, A Sweep Line algorithm.
- Song Ho’s explanation of the OpenGL GLU tesselator
- Шаблон:YouTube
- ↑ Шаблон:Citation
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation
- ↑ Шаблон:Citation Шаблон:Wayback
- ↑ Шаблон:Citation.
- ↑ Meisters, G. H., «Polygons have ears.»
- ↑ Шаблон:Статья
- ↑ Шаблон:Citation
- ↑ Toussaint, Godfried T. (1984), "A new linear algorithm for triangulating monotone polygons, " Pattern Recognition Letters, 2 (March):155-158.
- ↑ Pickover, Clifford A., The Math Book, Sterling, 2009: p. 184.
.svg){kind=link}