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

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

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

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

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

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

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

Деякі тріангуляції множини точок ${\displaystyle {\mathcal {P}}\subset \mathbb {R} ^{d}}$ можна отримати, якщо «підняти» точки ${\displaystyle {\mathcal {P}}}$ у простір ${\displaystyle \mathbb {R} ^{d+1}}$ (що означає додати координату ${\displaystyle x_{d+1}}$ для кожної точки ${\displaystyle {\mathcal {P}}}$), обчислити опуклу оболонку піднятої множини точок, і зробити проєкцію нижніх граней опуклої оболонки на ${\displaystyle \mathbb {R} ^{d}}$. Побудовані таким чином тріангуляції називають регулярними тріангуляціями ${\displaystyle {\mathcal {P}}}$. Якщо ж точки підняти на параболоїд, заданий рівнянням ${\displaystyle x_{d+1}=x_{1}^{2}+\cdots +x_{d}^{2}}$, ця конструкція стає тріангуляцією Делоне ${\displaystyle {\mathcal {P}}}$. Зауважте, що для того, щоб ця конструкція забезпечувала тріангуляцію, нижня опукла оболонка піднятої множини точок повинна бути симпліційною. Для тріангуляції Делоне це накладає вимогу, щоб ніякі ${\displaystyle d+2}$ точки ${\displaystyle {\mathcal {P}}}$ не лежали на одній сфері.

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

Кожна тріангуляція будь-якої множини ${\displaystyle {\mathcal {P}}}$ з ${\displaystyle n}$ точок в площині має ${\displaystyle 2n-h-2}$ трикутників і ${\displaystyle 3n-h-3}$ ребер, де ${\displaystyle h}$ — кількість точок множини ${\displaystyle {\mathcal {P}}}$, що належать опуклій оболонці ${\displaystyle {\mathcal {P}}}$. Це випливає безпосередньо з формули Ейлера^[5].

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

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

Інкрементальний алгоритм: Відсортувати точки ${\displaystyle {\mathcal {P}}}$ за x-координатами. Перші три точки визначають трикутник. Розглянемо наступну точку ${\displaystyle p}$ в упорядкованому наборі і з'єднаємо її з усіма раніше розглянутими точками ${\displaystyle \{p_{1},...,p_{k}\}}$, які видно з точки ${\displaystyle p}$. Процес додавання по одній точці з ${\displaystyle {\mathcal {P}}}$, продовжується доки не будуть оброблені всі точки^[7].

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

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

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

Див. також

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