Задача о триангуляции многоугольника
Задача о триангуляции многоугольника — классическая задача комбинаторной и вычислительной геометрии, состоящая в нахождении триангуляции многоугольника без дополнительных вершин.
Доказательство существования такой триангуляции не представляет сложности. Более того, эта задача всегда имеет решение для многоугольников с дырками, то есть областей плоскости, ограниченных несколькими замкнутыми ломаными.
Формулировка[править | править код]
Задача состоит в нахождении оптимального алгоритма триангуляции n-угольника без дополнительных вершин.
Эта задача может быть решена за линейное время, то есть задача имеет сложность .
История[править | править код]
Долгое время был открытым вопрос, можно ли найти триангуляцию n-угольника за время, меньше, чем .[1] Затем Ван Вик (1988) обнаружил алгоритм, требующий время ,[2] позже упрощённый Киркпатриком и Клаве.[3] Затем последовало несколько алгоритмов со сложностью (где — итерированный логарифм), не отличимых на практике от линейного времени.[4][5][6]
В 1991 году Бернард Чазелле доказал, что любой простой многоугольник может быть триангулирован в линейное время, хотя предложенный им алгоритм оказался очень сложным.[7] Также известен более простой вероятностный алгоритм с линейным ожидаемым временем.[8][9]
Алгоритмы[править | править код]
Отрезание ушей[править | править код]
Двойственный граф триангуляции без дополнительных вершин у простого многоугольника всегда является деревом. Отсюда в частности следует, что любой простой n-угольник с n > 3 имеет по меньшей мере два уха, то есть два треугольника, две стороны каждого из которых являются сторонами многоугольника, а третья полностью внутри него.[10]
Один из способов триангуляции состоит в нахождении такого уха и отрезании его от многоугольника. После этого ту же операцию повторно применяют к оставшемуся многоугольнику до тех пор, пока не останется один треугольник.
Этот способ работает только для многоугольников без дырок. Он прост в реализации, но работает медленнее, чем некоторые другие алгоритмы. Реализация, которая хранит отдельные списки выпуклых и вогнутых вершин, работает за время .
Эффективный алгоритм для отрезания ушей был предложен Хоссамом Эль-Гинди, Хэзелом Эвереттом и Годфридом Туссеном.[11]
Через монотонные многоугольники[править | править код]
Многоугольник называется монотонным, если его граничная ломаная имеет не более двух точек пересечения с прямой, перпендикулярной данной.
Монотонный многоугольник может быть триангулирован за линейное время с помощью алгоритма А. Фурнье и Д. Ю. Монтуно[12] или алгоритма Годфрид Туссен.[13]
Произвольный многоугольник может быть подразбит на монотонные. Алгоритм триангуляции простого многоугольника, построенный на этой идее, работает за время .
Вариации и обобщения[править | править код]
- Триангуляция многогранника без дополнительных вершин существует не всегда. Примером является Многогранник Шёнхардта, см. рисунок.
.svg)
- Триангуляция выпуклого многоугольника является тривиальной задачей. Она решается в линейное время путём проведения всевозможных диагоналей из одной вершины к остальным.
- Общее число способов триангулировать выпуклый -угольник диагоналями равно числу Каталана под номером , что было доказано Эйлером.[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.