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

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

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

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

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

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

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

История

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

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

Примечания

Mark de Berg, Marc van Kreveld, Mark Overmars and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag , ISBN 3-540-65620-0 {{ citation }} : Википедия:Обслуживание CS1 (множественные имена: authors list) ( ссылка )
Tarjan, Robert E.; Van Wyk, Christopher J. (1988), "An O( n log log n )-time algorithm for triangulating a simple polygon", SIAM Journal on Computing , 17 (1): 143—178, doi : , MR .
Kirkpatrick, David G.; Klawe, Maria M.; Tarjan, Robert E. (1992), "Polygon triangulation in O( n log log n ) time with simple data structures", Discrete and Computational Geometry , 7 (4): 329—346, doi : , MR .
Clarkson, Kenneth L.; Tarjan, Robert; van Wyk, Christopher J. (1989), "A fast Las Vegas algorithm for triangulating a simple polygon", Discrete and Computational Geometry , 4 : 423—432, doi : .
Seidel, Raimund (1991), "A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons", Computational Geometry: Theory and Applications , 1 : 51—64, doi :
Clarkson, Kenneth L.; Cole, Richard; Tarjan, Robert E. (1992), "Randomized parallel algorithms for trapezoidal diagrams", International Journal of Computational Geometry & Applications , 2 (2): 117—133, doi : , MR .
Chazelle, Bernard (1991), "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry , 6 : 485—524, doi : , ISSN
Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), , Discrete & Computational Geometry , 26 (2): 245—265, doi : , ISSN . Дата обращения: 28 мая 2016. Архивировано из 23 июля 2018 года.
Li, Fajie; Klette, Reinhard (2011), Euclidean Shortest Paths , , doi : , ISBN 978-1-4471-2255-5 .
Meisters, G. H., «Polygons have ears.»
ElGindy, H.; Everett, H.; Toussaint, G. T. Slicing an ear using prune-and-search (англ.) // (англ.) ( : journal. — 1993. — Vol. 14 , no. 9 . — P. 719—722 . — doi : .
Fournier, A.; Montuno, D. Y. (1984), "Triangulating simple polygons and equivalent problems", , 3 (2): 153—174, doi : , ISSN
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.