Задача о триангуляции многоугольника ({g;gcg k mjnguirlxenn bukikrikl,untg)

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

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

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

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

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

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

История

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

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

Примечания

↑ 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:10.1137/0217010, MR 0925194.
↑ 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:10.1007/BF02187846, MR 1148949.
↑ 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:10.1007/BF02187741.
↑ 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:10.1016/0925-7721(91)90012-4
↑ 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:10.1142/S0218195992000081, MR 1168952.
↑ Chazelle, Bernard (1991), "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 6: 485—524, doi:10.1007/BF02574703, ISSN 0179-5376
↑ Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), "A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 26 (2): 245—265, doi:10.1007/s00454-001-0027-x, ISSN 0179-5376, Архивировано из оригинала 23 июля 2018, Дата обращения: 28 мая 2016 Источник (неопр.). Дата обращения: 28 мая 2016. Архивировано из оригинала 23 июля 2018 года.
↑ Li, Fajie; Klette, Reinhard (2011), Euclidean Shortest Paths, Springer, doi:10.1007/978-1-4471-2256-2, 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 (англ.) // Pattern Recognition Letters^[англ.] : journal. — 1993. — Vol. 14, no. 9. — P. 719—722. — doi:10.1016/0167-8655(93)90141-y.
↑ Fournier, A.; Montuno, D. Y. (1984), "Triangulating simple polygons and equivalent problems", ACM Transactions on Graphics, 3 (2): 153—174, doi:10.1145/357337.357341, ISSN 0730-0301
↑ 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.

Ссылки

Demo as Flash swf, A Sweep Line algorithm.
Song Ho’s explanation of the OpenGL GLU tesselator
Every Polygon can be Triangulated Into Exactly n-2 Triangles: Proof by Induction на YouTube

[bkos-1] 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) (ссылка)

[2] 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:10.1137/0217010, MR 0925194.

[3] 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:10.1007/BF02187846, MR 1148949.

[4] 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:10.1007/BF02187741.

[5] 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:10.1016/0925-7721(91)90012-4

[6] 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:10.1142/S0218195992000081, MR 1168952.

[7] Chazelle, Bernard (1991), "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 6: 485—524, doi:10.1007/BF02574703, ISSN 0179-5376

[8] Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), "A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 26 (2): 245—265, doi:10.1007/s00454-001-0027-x, ISSN 0179-5376, Архивировано из оригинала 23 июля 2018, Дата обращения: 28 мая 2016 Источник (неопр.). Дата обращения: 28 мая 2016. Архивировано из оригинала 23 июля 2018 года.

[9] Li, Fajie; Klette, Reinhard (2011), Euclidean Shortest Paths, Springer, doi:10.1007/978-1-4471-2256-2, ISBN 978-1-4471-2255-5.

[10] Meisters, G. H., «Polygons have ears.»

[11] ElGindy, H.; Everett, H.; Toussaint, G. T. Slicing an ear using prune-and-search (англ.) // Pattern Recognition Letters^[англ.] : journal. — 1993. — Vol. 14, no. 9. — P. 719—722. — doi:10.1016/0167-8655(93)90141-y.

[12] Fournier, A.; Montuno, D. Y. (1984), "Triangulating simple polygons and equivalent problems", ACM Transactions on Graphics, 3 (2): 153—174, doi:10.1145/357337.357341, ISSN 0730-0301

[13] Toussaint, Godfried T. (1984), "A new linear algorithm for triangulating monotone polygons, " Pattern Recognition Letters, 2 (March):155-158.

[14] Pickover, Clifford A., The Math Book, Sterling, 2009: p. 184.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]