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

Деякі тріангуляції множини точок ${\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-складний (тріангуляція мінімальної ваги)
мінімум	висота		${\displaystyle O(n^{2}\log n)}$[9]
максимум	нахил	${\displaystyle O(n^{3})}$[9]

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