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

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

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

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

ФормулировкаПравить

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

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

ИсторияПравить

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

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

АлгоритмыПравить

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

Отрезание ушейПравить

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

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

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

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

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

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

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

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

Вариации и обобщенияПравить

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

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

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

Триангуляция выпуклого многоугольника является тривиальной задачей. Она решается в линейное время путём проведения всевозможных диагоналей из одной вершины к остальным.
- Общее число способов триангулировать выпуклый $\text{[math]}$ $\text{[math]}$ $n$ -угольник диагоналями равно числу Каталана под номером $\text{[math]}$ $\text{[math]}$ $(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
↑ 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 .
↑ 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 .
↑ 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 .
↑ Chazelle, Bernard (1991), Triangulating a Simple Polygon in Linear Time, Discrete & Computational Geometry Т. 6: 485–524, ISSN 0179-5376, DOI 10.1007/BF02574703
↑ 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, ISSN 0179-5376, doi:10.1007/s00454-001-0027-x, <http://parasol.tamu.edu/publications/abstract.php?pub_id=185> Архивная копия от 23 июля 2018 на Wayback Machine
↑ Li, Fajie & Klette, Reinhard (2011), Euclidean Shortest Paths, Springer, ISBN 978-1-4471-2255-5, DOI 10.1007/978-1-4471-2256-2 .
↑ 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, ISSN 0730-0301, DOI 10.1145/357337.357341
↑ 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

[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 .

[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 .

[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 .

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

[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, ISSN 0179-5376, doi:10.1007/s00454-001-0027-x, <http://parasol.tamu.edu/publications/abstract.php?pub_id=185> Архивная копия от 23 июля 2018 на Wayback Machine

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

[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, ISSN 0730-0301, DOI 10.1145/357337.357341

[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]