Триангуляция Делоне
В математике и вычислительной геометрии триангуляция Делоне ( также известная как триангуляция Делоне ) для заданного множества P дискретных точек в общем положении — это триангуляция DT( P ), такая что ни одна точка в P не находится внутри описанной окружности любого треугольника в ДТ( П ). Триангуляции Делоне максимизируют минимальный угол всех углов треугольников в триангуляции; они, как правило, избегают узких треугольников . Триангуляция названа в честь Бориса Делоне .за его работу по этой теме с 1934 г. [1]
Для множества точек на одной прямой триангуляции Делоне нет (понятие триангуляции в этом случае вырождено). Для четырех или более точек на одной и той же окружности (например, вершин прямоугольника) триангуляция Делоне не уникальна: каждая из двух возможных триангуляций, разбивающих четырехугольник на два треугольника, удовлетворяет «условию Делоне», т. е. требованию, чтобы описанные окружности всех треугольников имеют пустые внутренности.
При рассмотрении описанных сфер понятие триангуляции Делоне распространяется на три и более измерения. Обобщения возможны для метрик , отличных от евклидова расстояния . Однако в этих случаях существование или уникальность триангуляции Делоне не гарантируется.
Триангуляция Делоне дискретного множества точек P общего положения соответствует двойственному графу диаграммы Вороного для P . Центры описанных окружностей треугольников Делоне являются вершинами диаграммы Вороного. В двумерном случае вершины Вороного соединены ребрами, которые могут быть получены из отношений смежности треугольников Делоне: если два треугольника имеют общее ребро в триангуляции Делоне, их центры описанных окружностей должны быть соединены ребром в мозаике Вороного. .
Для множества P точек в ( d - мерном) евклидовом пространстве триангуляция Делоне есть триангуляция DT( P ) такая , что ни одна точка в P не находится внутри описанной гиперсферы любого d - симплекса в DT( P ). Известно [1] , что существует единственная триангуляция Делоне для P , если P — множество точек общего положения ; то есть аффинная оболочка P является d -мерной и никакое множество d + 2 точки из P лежат на границе шара, внутренность которого не пересекает P .
Задача нахождения триангуляции Делоне множества точек в d - мерном евклидовом пространстве может быть преобразована в задачу нахождения выпуклой оболочки множества точек в ( d + 1)-мерном пространстве. Это можно сделать, задав каждой точке p дополнительную координату, равную | р | 2 , превращая его таким образом в гиперпараболоид (это называется «подъемом»); взятие нижней стороны выпуклой оболочки (поскольку верхняя торцевая крышка обращена вверх от начала координат и должна быть отброшена); и отображение обратно в d-мерное пространство, удалив последнюю координату. Поскольку выпуклая оболочка уникальна, то и триангуляция уникальна, если предположить, что все грани выпуклой оболочки являются симплексами . Несимплицитные грани возникают только тогда, когда d + 2 исходных точек лежат на одной и той же d - гиперсфере , т. е. точки не находятся в общем положении. [2]
.svg)