Тріангуляція множини точок

Тріангуляція множини точок в евклідовому просторі  — це симпліціальний комплекс, що охоплює опуклу оболонку , і вершини якого належать [1]. У площині (коли  — це множина точок з ), триангуляція складається з трикутників разом із їхніми ребрами та вершинами. Деякі автори вимагають, щоб усі точки були вершинами його тріангуляції[2]. У цьому випадку тріангуляція множини точок в площині можна також визначити як максимальний набір ребер, які не перетинаються та з'єднують точки . У площині, тріангуляція — це особливі випадки плоских прямолінійних графів.

Двв різні трикутники одного і того ж набору з 9 точок у площині.

Особливо цікавими видами тріангуляції є тріангуляція Делоне, яка геометрично є дуальною до діаграми Вороного. Тріангуляція Делоне множини точок у площині містить граф Габрієла, граф найближчих сусідів та мінімальне кістякове дерево точок .

Тріангуляція має численні застосування, та існує сенс у побудові «гарних» тріангуляцій множини точок за певними критеріями, наприклад, тріангуляція мінімальної ваги. Іноді бажано мати тріангуляції зі спеціальними властивостями, наприклад, коли всі трикутники мають великі кути, що, в свою чергу, дозволяє уникнути довгих та вузьких «осколкових» трикутників[3].

Для заданої множини ребер, що з'єднують точки площини, задача визначення того, чи містять вони триангуляцію, є NP-повною[4].

Регулярні триангуляції

Деякі тріангуляції множини точок можна отримати, якщо «підняти» точки у простір (що означає додати координату для кожної точки ), обчислити опуклу оболонку піднятої множини точок, і зробити проекцію нижніх граней опуклої оболонки на . Побудовані таким чином тріангуляції називають регулярними тріангуляціями . Якщо ж точки підняти на параболоїд, заданий рівнянням , ця конструкція стає триангуляцією Делоне . Зауважте, що для того, щоб ця конструкція забезпечувала тріангуляцію, нижня опукла оболонка піднятої множини точок повинна бути симпліціальною. Для тріангуляції Делоне це накладає вимогу, щоб ніякі точки не лежали на одній сфері.

Комбінаторика в площині

Кожна тріангуляція будь-якої множини з точок в площині має трикутників і ребер, де  — кількість точок множини , що належать опуклій оболонці . Це випливає безпосередньо з формули Ейлера[5].

Алгоритми побудови тріангуляції у площині

Алгоритм розщеплення трикутника: Знайдіть опуклу оболонку множини точок і тріангулюйте цю оболонку як багатокутник. Для кожної внутрішньої точки додайте ребра, які з'єднують її з трьома вершина трикутника, якому вона належить. Цей процес продовжується, доки не будуть вичерпані всі внутрішні точки[6].

Інкрементальний алгоритм: Відсортувати точки за x-координатами. Перші три точки визначають трикутник. Розглянемо наступну точку в упорядкованому наборі і з'єднаємо її з усіма раніше розглянутими точками , які видно з точки . Процес додавання по одній точці з , продовжується доки не будуть оброблені всі точки[7].

Часова складність різних алгоритмів

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

мінімізувати максимізувати
мінімум кут
(тріангуляція Делоне)
максимум [8][9]
мінімум площа [10] [11]
максимум [11]
максимум степінь NP-повна
для степені 7[12]
максимум ексцентриситет [9]
мінімум довжина ребра
(найближча пара точок)
NP-повна[13]
максимум [14]
(за допомогою опуклої оболонки)
сума NP-складний
(тріангуляція мінімальної ваги)
мінімум висота [9]
максимум нахил [9]

Див. також

Примітки

  1. De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010). Triangulations, Structures for Algorithms and Applications. Algorithms and Computation in Mathematics 25. Springer.
  2. de Berg та ін., 2008, Section 9.1.
  3. de Berg, Mark; Otfried Cheong; Marc van Kreveld; Mark Overmars (2008). Computational Geometry: Algorithms and Applications. Springer-Verlag. ISBN 978-3-540-77973-5.
  4. Lloyd, 1977.
  5. Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman (1992). An O(n2 log n) time algorithm for the minmax angle triangulation. SIAM Journal on Scientific and Statistical Computing 13 (4): 994–1008. MR 1166172. doi:10.1137/0913058..
  6. Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 60.
  7. Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 62.
  8. Edelsbrunner, Tan та Waupotitsch, 1990.
  9. Bern та ін., 1993.
  10. Chazelle, Guibas та Lee, 1985.
  11. Vassilev, 2005.
  12. Jansen, 1992.
  13. Fekete, 2012.
  14. Edelsbrunner та Tan, 1991.

Список літератури

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.