Триангуляция по заданным точкам

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

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

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

Триангуляции имеют ряд приложений, и есть интерес найти "хорошие" триангуляции заданного набора точек при некоторых критериях, таких как, например, триангуляции с минимальным весом . Иногда желательно иметь триангуляцию с особыми свойствами, например, в которой все треугольники имеют большие углы (избегаются длинные и узкие («осколочные») треугольники). ^[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}}}$

Комбинаторика на плоскости [ править ]

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

Алгоритмы построения триангуляции на плоскости [ править ]

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

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

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

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

		минимизировать	максимизировать
минимум	угол		${\ Displaystyle О (п \ журнал п)}$ ( Триангуляция Делоне )
максимум		${\ Displaystyle О (п ^ {2} \ журнал п)}$ [8] [9]
минимум	область	${\displaystyle O(n^{2})}$ [10]	${\displaystyle O(n^{2}\log n)}$ [11]
максимум		${\displaystyle O(n^{2}\log n)}$ [11]
максимум	степень	НП-полный для 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]

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]