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

Триангуляцией Делоне для множества точек S на плоскости называют триангуляцию DT(S), такую что никакая точка A из S не содержится внутри окружности, описанной вокруг любого треугольника из DT(S), такого, что ни одной из вершин его не является точка A.

Эта триангуляция впервые описана Борисом Делоне.

Свойства

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

Алгоритм "Разделяй и Властвуй"

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

1. Разбиение исходного множества на более мелкие множества. Для этого мы проводим вертикальные или горизонтальные прямые в середине множества и уже относительно этих прямых разделяем точки на две части примерно по N/2. После для каждой группы точек рекурсивно запускаем процесс деления в зависимости от их количества:
   1. Если число точек N>12, то делим множество с помощью прямых.
   2. Если число точек N<=12, то делим множество на 3 и N-3 точек.
   3. Если число точек N=8, то делим множество на 2 группы по 4 точки. Деление продолжается до тех пор, пока не останется 3 или 4 точки.
2. Построение триангуляции для множеств из 3 или 4 точек. Для трех точек триангуляция очевидна — просто соединяем попарно точки отрезками. Для четырех точек возможны два варианта:
   1. Если точки образуют не выпуклый четырехугольник, то просто соединяем все 4 точки отрезками.
   2. Если точки образуют выпуклый четырехугольник, то берем любые 3 точки и проверяем положение четвертой точки относительно окружности, описанной вокруг первых трех точек. Здесь возможны три варианта:
      1. Точка лежит за пределами окружности. Данная триангуляция оптимальна, строим треугольник из первых трех точек и соединяем с четвертой ближайшие к ней 2 точки.
      2. Точка лежит внутри окружности. В этом случае нарушается условие триангуляции Делоне, и отрезками соединяются четвертая точка со всеми остальными точками, а также те точки, отрезки между которыми не создадут пересечений с уже проведенными отрезками.
      3. Точка лежит на окружности. В этом случае любая триангуляция оптимальна.
3. Объединение оптимальных триангуляций. Сначала находятся две пары точек, отрезки которых образуют в совокупности с построенными триангуляциями выпуклую фигуру. Они соединяются отрезками, и один из полученных отрезков выбирается как начало для последующего обхода. Обход заключается в следующем: на этом отрезке мы как будто «надуваем пузырь» вовнутрь до первой точки, которую достигнет раздувающаяся окружность «пузыря». С найденной точкой соединяется та точка отрезка, которая не была с ней соединена. Полученный отрезок проверяется на пересечение с уже существующими отрезками триангуляции, и в случае пересечения они удаляются из триангуляции. После этого новый отрезок принимается за начало для нового «пузыря». Цикл повторяется до тех пор, пока начало не совпадет со вторым отрезком выпуклой оболочки.

Сложность разбиения множества О(logN), объединения — O(N) для каждого объединения, итоговая сложность алгоритма — O(NlogN).^[2]

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

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

Применение

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

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

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

См. также

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

Примечания