Триангуляция множества точек в евклидовом пространстве — это симплициальный комплекс, который покрывает выпуклую оболочку , чьи вершины принадлежат . На плоскости (когда — это множество точек в ), триангуляции состоят из треугольников, а также их рёбер и вершин. Некоторые авторы требуют, чтобы все точки были вершинами триангуляции. В этом случае триангуляция множества точек на плоскости может быть альтернативно определена как максимальное множество непересекающихся рёбер между точками . На плоскости триангуляции являются частными случаями планарных прямолинейных графов.
Одним из видов триангуляций является триангуляция Делоне. Такие триангуляции являются геометрическими двойниками диаграмм Вороного. Триангуляция Делоне множества точек на плоскости содержит граф Габриэля, граф ближайших соседей и минимальное остовное дерево .
Триангуляции имеют множество применений, и существует интерес к поиску «хороших» триангуляций заданного набора точек по определённым критериям, например, триангуляций с . Иногда желательно получить триангуляцию с особыми свойствами, например, в которой все треугольники имеют большие углы (избегаются длинные и узкие («осколочные») треугольники).
Задача определения, содержат ли заданный набор рёбер, соединяющих точки плоскости, триангуляцию, является NP-полной.
Регулярные триангуляризации Некоторые триангуляции набора точек могут быть получены путём поднятия точек в (что сводится к добавлению координаты к каждой точке ), вычисления выпуклой оболочки поднятого набора точек и последующего проецирования нижних граней этой выпуклой оболочки обратно на . Триангуляции, построенные таким образом, называются регулярными триангуляциями . Когда точки поднимаются на параболоид с уравнением , эта конструкция приводит к триангуляции Делоне набора точек . Для того, чтобы эта конструкция давала триангуляцию, нижняя выпуклая оболочка поднятого набора точек должна быть симплициальной. В случае триангуляции Делоне, это означает требование, чтобы никакие точки из не лежали на одной сфере.
Варианты и расширения
Помимо классических триангуляций Делоне и регулярных триангуляций в вычислительной геометрии изучались и другие формы и задачи, связанные с триангуляциями множеств точек. Триангуляция с минимальным весом стремится найти такую триангуляцию множества точек, которая минимизирует общую длину рёбер. Хотя было показано, что эта задача NP-трудна, для неё были разработаны аппроксимационные алгоритмы и эвристики. Связанная эвристика, жадная триангуляция, строит триангуляцию путём многократного добавления кратчайшего ребра, которое не пересекает существующие рёбра, что на практике даёт хорошие приближения. Другой особый тип — , в которой каждое ребро соединяет пару точек, чьи ячейки Вороного имеют общий граничный сегмент. Такие триангуляции тесно связаны с графами Делоне и Габриэля. Триангуляции множеств точек также можно рассматривать как максимальные планарные прямолинейные графы, поскольку никакие дополнительные прямые рёбра не могут быть добавлены без нарушения планарности. В последнее время были предложены подходы машинного обучения для генерации триангуляций непосредственно из неструктурированных облаков точек, такие как алгоритм PointTriNet, который использует нейронные сети для изучения паттернов триангуляции для двумерных и трёхмерных данных. Достижения в комбинаторной геометрии также привели к новым оценкам числа различных триангуляций, реализуемых на фиксированном множестве точек, подчёркивая экспоненциальную сложность этих структур.
Комбинаторика на плоскости Любая триангуляция любого набора из точек на плоскости имеет треугольников и рёбер, где — число точек набора на границе выпуклой оболочки . Это непосредственно следует из эйлеровой характеристики.
Алгоритмы построения триангуляризации на плоскости Алгоритм разделения треугольника : Строим выпуклую оболочку набора точек и разбиваем полученный многоугольник на треугольники. Выбираем внутреннюю точку и рисуем рёбра, соединяющие эту точку с вершинами треугольника, её содержащего. Продолжаем процесс, пока не будут исчерпаны все внутренние точки.
Инкрементирующий алгоритм: Сортируем точки множества по координате x. Первые три точки образуют треугольник. Рассмотрим следующую точку в упорядоченном наборе и соединяем её со всеми ранее рассмотренными точками , которые видны из p. Продолжаем процесс добавления по одной точке из , пока все точки не будут обработаны .
Временна́я сложность различных алгоритмов
В следующей таблице представлены результаты временно́й сложности для построения триангуляций множеств точек на плоскости при различных критериях оптимальности, где — количество точек.
минимум максимум минимум угол (Триангуляция Делоне) максимум минимум площадь максимум максимум степень NP-полная задача для степени 7 максимум эксцентриситет максимум длина ребра (Задача о паре ближайших точек) NP-полная максимум (используя выпуклую оболочку) сумма NP-трудная () минимум высота максимум наклон
См. также
Задача о триангуляции многоугольника
Примечания
Литература
Замечание: Две практически идентичных книги, отличающиеся одной фамилией авторов, хотя это тот же самый человек (немецкий геометр Schwarzkopf, работавший в Южной Корее под фамилией Cheong). Ниже перевод данной книги.
Тезисы диссертации Ph.D.
Категория:Планарные графы Категория:Элементарная геометрия