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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігаціїПерейти до пошуку
Двв різні трикутники одного і того ж набору з 9 точок у площині.

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

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

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

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

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

ред. код

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

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

ред. код

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

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

ред. код

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

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

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

ред. код

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

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

Див. також

ред. код

Примітки

ред. код

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

ред. код

Навігаційне меню