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

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

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

Свойства

• Триангуляция Делонe максимизирует минимальный угол среди всех углов всех построенных треугольников, тем самым избегаются «тонкие» треугольники.
• Триангуляция Делоне взаимно однозначно соответствует диаграмме Вороного для того же набора сайтов.
• Триангуляция Делоне максимизирует сумму радиусов вписанных шаров.
• Триангуляция Делоне минимизирует дискретный функционал Дирихле.
• Триангуляция Делоне минимизирует максимальный радиус минимального объемлющего шара.
• Триангуляция Делоне на плоскости обладает минимальной суммой радиусов окружностей, описанных около треугольников, среди всех возможных триангуляций. ^[1].
• Триангуляция Делоне используется при ортотрансформировании изображений, построенных по законам нецентральной проекции (способ "резинового листа").
• Триангуляция Делоне используется в модуле визуализации программы трёхмерного моделирования 3D Studio MAX - V-Ray компании Chaos Group.

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

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

Примечания