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

Для более широкого освещения этой темы см. Триангуляция (геометрия) .

Две разные триангуляции одного и того же набора из 9 точек на плоскости.

Триангуляция набора точек ${\mathcal {P}}$ в евклидовом пространстве $\mathbb {R} ^{d}$ является симплициальным комплексом , покрывающим выпуклую оболочку ${\mathcal {P}}$, и чьи вершины принадлежат ${\mathcal {P}}$. В самолете (когда ${\mathcal {P}}$ представляет собой набор точек в $\mathbb {R} ^{2}$), триангуляции состоят из треугольников вместе с их ребрами и вершинами. Некоторые авторы требуют, чтобы все пункты ${\mathcal {P}}$ являются вершинами его триангуляций. В этом случае триангуляция множества точек ${\mathcal {P}}$ в плоскости можно альтернативно определить как максимальный набор непересекающихся ребер между точками ${\mathcal {P}}$. На плоскости триангуляции — это частные случаи плоских прямолинейных графов .

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

Триангуляции имеют ряд применений, и существует интерес найти «хорошие» триангуляции данного набора точек при некоторых критериях, например, триангуляции с минимальным весом . Иногда желательно иметь триангуляцию с особыми свойствами, например, в которой все треугольники имеют большие углы (длинных и узких («осколочных») треугольников следует избегать).

Учитывая набор ребер, соединяющих точки плоскости, задача определить, содержат ли они триангуляцию, является NP-полной .

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

Некоторые триангуляции множества точек ${\mathcal {P}}\subset \mathbb {R} ^{d}$ можно получить, подняв точки ${\mathcal {P}}$ в $\mathbb {R} ^{d+1}$ (что равнозначно добавлению координаты $x_{d+1}$ в каждую точку ${\mathcal {P}}$), вычисляя выпуклую оболочку поднятого множества точек и проецируя нижние грани этой выпуклой оболочки обратно на $\mathbb {R} ^{d}$. Построенные таким образом триангуляции называются правильными триангуляциями ${\mathcal {P}}$. Когда точки подняты на параболоид уравнения $x_{d+1}=x_{1}^{2}+\cdots +x_{d}^{2}$, эта конструкция приводит к триангуляции Делоне ${\mathcal {P}}$. Обратите внимание, что для того, чтобы эта конструкция обеспечивала триангуляцию, нижняя выпуклая оболочка поднятого множества точек должна быть симплициальной . В случае триангуляций Делоне это означает, что не требуется, чтобы $d+2$ точки ${\mathcal {P}}$ лежат в одной сфере.

Комбинаторика на плоскости

Любая триангуляция любого множества ${\mathcal {P}}$ из $n$ точки на плоскости имеют $2n-h-2$ треугольники и $3n-h-3$ края, где $h$ это количество точек ${\mathcal {P}}$ на границе выпуклой оболочки ${\mathcal {P}}$. Это следует из простого характеристического аргумента Эйлера .

Алгоритмы построения триангуляций на плоскости

Алгоритм разделения треугольников : найдите выпуклую оболочку набора точек. ${\mathcal {P}}$ и триангулируйте эту оболочку как многоугольник. Выберите внутреннюю точку и нарисуйте края к трем вершинам треугольника, который ее содержит. Продолжайте этот процесс, пока все внутренние точки не будут исчерпаны.

Инкрементный алгоритм : сортировка точек ${\mathcal {P}}$ по координатам х. Первые три точки определяют треугольник. Рассмотрим следующий момент $p$ в упорядоченном множестве и соединить его со всеми ранее рассмотренными точками $\{p_{1},...,p_{k}\}$ которые видны на стр. Продолжайте этот процесс, добавляя одну точку ${\mathcal {P}}$ одновременно, пока все ${\mathcal {P}}$ был обработан.

Временная сложность различных алгоритмов

В следующей таблице представлены результаты временной сложности для построения триангуляций наборов точек на плоскости при различных критериях оптимальности, где $n$ это количество очков.

		минимизировать	максимизировать
минимум	угол		$O(n\log n)$ ( Триангуляция Делоне )
максимум		$O(n^{2}\log n)$
минимум	область	$O(n^{2})$	$O(n^{2}\log n)$
максимум		$O(n^{2}\log n)$
максимум	степень	NP-полный для 7 степени
максимум	эксцентричность	$O(n^{3})$
минимум	длина кромки	$O(n\log n)$ ( Задача о ближайшей паре точек )	NP-полный
максимум		$O(n^{2})$	$O(n\log n)$ (с использованием выпуклой оболочки )
сумма		NP-жесткий ( Триангуляция минимального веса )
минимум	высота		$O(n^{2}\log n)$
максимум	склон	$O(n^{3})$

См. также

• Генерация сетки
• Триангуляция многоугольника

Ссылки

• Берн, М.; Эдельсбруннер, Х. ; Эппштейн, Д .; Митчелл, С.; Тан, Т.С. (1993), «Вставка ребер для оптимальной триангуляции», Дискретная и вычислительная геометрия , 10 (1): 47–65, doi : 10.1007/BF02573962 , MR   1215322
• Шазель, Бернар; Гибас, Лео Дж.; Ли, DT (1985). «Сила геометрической двойственности» (PDF) . КУСОЧЕК . 25 (1). БИТ Информатики и числовой математики: 76–90. дои : 10.1007/BF01934990 . ISSN   0006-3835 . S2CID   122411548 .
• де Берг, Марк; ван Кревелд, Марк; Овермарс, Марк; Шварцкопф, Отфрид (2008). Вычислительная геометрия: алгоритмы и приложения (3-е изд.). Издательство Спрингер.
• О'Рурк, Джозеф; Л. Девадосс, Сатьян (2011). Дискретная и вычислительная геометрия (1-е изд.). Издательство Принстонского университета.
• Эдельсбруннер, Герберт; Тан, Тиоу Сенг; Ваупотич, Роман (1990). Алгоритм времени O(n2log n) для триангуляции углов MinMax . Материалы шестого ежегодного симпозиума по вычислительной геометрии. СКГ '90. АКМ. стр. 44–52. CiteSeerX   10.1.1.66.2895 . дои : 10.1145/98524.98535 . ISBN  0-89791-362-0 .
• Эдельсбруннер, Герберт; Тан, Тиоу Сенг (1991). Алгоритм квадратичного времени для триангуляции минимальной и максимальной длины . 32-й ежегодный симпозиум по основам информатики. стр. 414–423. CiteSeerX   10.1.1.66.8959 . дои : 10.1109/SFCS.1991.185400 . ISBN  0-8186-2445-0 .
• Фекете, Шандор П. (2012). «Сложность триангуляции длины MaxMin». arXiv : 1208.0202v1 [ cs.CG ].
• Янсен, Клаус (1992). Сложность задачи триангуляции минимально-максимальной степени (PDF) . 9-й Европейский семинар по вычислительной геометрии. стр. 40–43.
• Ллойд, Эррол Линн (1977). О триангуляциях множества точек плоскости . 18-й ежегодный симпозиум по основам информатики. Теория коммутации и автоматов, 1974 г., Протокол конференции IEEE 15-го ежегодного симпозиума по . стр. 228–240. дои : 10.1109/SFCS.1977.21 . ISSN   0272-5428 .
• Васильев, Цветалин Симеонов (2005). Триангуляция оптимальной области (PDF) (доктор философии). Университет Саскачевана, Саскатун. Архивировано из оригинала (PDF) 13 августа 2017 г. Проверено 15 июня 2013 г.