Триангуляция Делоне

Пример триангуляции Делоне. Из каждой точки порождается окружность, проходящая через две ближайшие в метрике Евклида точки.

Триангуля́ция Делоне́ — триангуляция для заданного множества точек S на плоскости, при которой для любого треугольника все точки из S за исключением точек, являющихся его вершинами, лежат вне окружности, описанной вокруг треугольника. Обозначается DT(S). Впервые описана в 1934 году советским математиком Борисом Делоне.

Свойства

• Триангуляция Делоне взаимно однозначно соответствует диаграмме Вороного для того же множества точек.
• Как следствие: если никакие четыре точки не лежат на одной окружности, триангуляция Делоне единственна.
• Триангуляция Делоне максимизирует минимальный угол среди всех углов всех построенных треугольников, тем самым избегаются «тонкие» треугольники.
• Триангуляция Делоне максимизирует сумму радиусов вписанных окружностей.
• Триангуляция Делоне минимизирует дискретный функционал Дирихле.
• Триангуляция Делоне минимизирует максимальный радиус минимального объемлющего шара.
• Триангуляция Делоне на плоскости обладает минимальной суммой радиусов окружностей, описанных около треугольников, среди всех возможных триангуляций.

Алгоритм «разделяй и властвуй»

Данный алгоритм основан на стандартной для многих алгоритмов методике сведения сложной задачи к более простым, в которых решение очевидно. Сам алгоритм для $N>1$ состоит из 2 шагов:

1. Разбиение исходного множества на более мелкие множества. Для этого мы проводим вертикальные или горизонтальные прямые в середине множества и уже относительно этих прямых разделяем точки на две части примерно по $N/2$. После для каждой группы точек рекурсивно запускаем процесс деления.
2. Объединение оптимальных триангуляций. Сначала находятся две пары точек, отрезки которых образуют в совокупности с построенными триангуляциями выпуклую фигуру. Они соединяются отрезками, и один из полученных отрезков выбирается как начало для последующего обхода. Обход заключается в следующем: на этом отрезке мы как будто «надуваем пузырь» внутрь до первой точки, которую достигнет раздувающаяся окружность «пузыря». С найденной точкой соединяется та точка отрезка, которая не была с ней соединена. Полученный отрезок проверяется на пересечение с уже существующими отрезками триангуляции, и в случае пересечения они удаляются из триангуляции. После этого новый отрезок принимается за начало для нового «пузыря». Цикл повторяется до тех пор, пока начало не совпадёт со вторым отрезком выпуклой оболочки.

Сложность разбиения множества $O(\log N)$, объединения — $O(N)$ для каждого объединения, итоговая сложность алгоритма — $O(N\log N)$.

Вариации и обобщения

• В трёхмерном пространстве возможна аналогичная конструкция с заменой окружностей на сферы.
• Также используются и обобщения при введении метрик, отличных от евклидовой.
• Одно из свойств триангуляции Делоне — минимальная сумма радиусов описанных кругов — можно применить для так называемой ограниченной триангуляции Делоне. Есть n точек, часть рёбер триангуляции уже проведены; провести остальные, чтобы сумма радиусов описанных кругов была наименьшей.

Применение

Минимальное евклидово остовное дерево гарантированно располагается на триангуляции Делоне, поэтому некоторые алгоритмы пользуются триангуляцией. Также через триангуляцию Делоне приближённо решается евклидова задача о коммивояжёре.

В двумерной интерполяции триангуляция Делоне разбивает плоскость на самые «толстые» треугольники, насколько это возможно, избегая слишком острых и слишком тупых углов. По этим треугольникам можно строить, например, билинейную интерполяцию.

Метод конечных элементов — метод численного решения дифференциальных уравнений в частных производных — предельно универсален, и с ростом мощи компьютеров и с отработкой стандартных библиотек становится всё более популярным. Однако построение конечноэлементной сетки до последнего времени оставалось ручной работой. В большинстве вариантов метода конечных элементов погрешность обратно пропорциональна синусу минимального или максимального угла сетки, поэтому многие из алгоритмов автоматического построения сетки используют триангуляцию Делоне.

См. также

• Квазитриангуляция

Литература

• Скворцов А. В. Триангуляция Делоне и её применение. — Томск: Изд-во Томского университета, 2002. — 128 с. — ISBN 5-7511-1501-5.
• Скворцов А. В., Мирза Н. С. Алгоритмы построения и анализа триангуляции. — Томск: Изд-во Томского университета, 2006. — 168 с. — ISBN 5-7511-2028-0.