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

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

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

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

Свойства

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

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

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

Применение

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

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

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