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

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

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

Свойства[править | править вики-текст]

  • Триангуляция Делоне взаимно однозначно соответствует диаграмме Вороного для того же множества точек.
  • Как следствие: если никакие четыре точки не лежат на одной окружности, триангуляция Делоне единственна.
  • Триангуляция Делоне максимизирует минимальный угол среди всех углов всех построенных треугольников, тем самым избегаются «тонкие» треугольники.
  • Триангуляция Делоне максимизирует сумму радиусов вписанных шаров.
  • Триангуляция Делоне минимизирует дискретный функционал Дирихле.
  • Триангуляция Делоне минимизирует максимальный радиус минимального объемлющего шара.
  • Триангуляция Делоне на плоскости обладает минимальной суммой радиусов окружностей, описанных около треугольников, среди всех возможных триангуляций.[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. Объединение оптимальных триангуляций. Сначала находятся две пары точек, отрезки которых образуют в совокупности с построенными триангуляциями выпуклую фигуру. Они соединяются отрезками, и один из полученных отрезков выбирается как начало для последующего обхода. Обход заключается в следующем: на этом отрезке мы как будто «надуваем пузырь» вовнутрь до первой точки, которую достигнет раздувающаяся окружность «пузыря». С найденной точкой соединяется та точка отрезка, которая не была с ней соединена. Полученный отрезок проверяется на пересечение с уже существующими отрезками триангуляции, и в случае пересечения они удаляются из триангуляции. После этого новый отрезок принимается за начало для нового «пузыря». Цикл повторяется до тех пор, пока начало не совпадет со вторым отрезком выпуклой оболочки.

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

Вариации и обобщения[править | править вики-текст]

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

Применение[править | править вики-текст]

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

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

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

См. также[править | править вики-текст]

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

Примечания[править | править вики-текст]

  1. Скворцов А. В. Триангуляция Делоне и её применение. Томск: Изд-во Томского университета, 2002. 128 с. ISBN 5-7511-1501-5, теорема 3 на стр. 11
  2. Скворцов А. В. Триангуляция Делоне и её применение. Томск: Изд-во Томского университета, 2002. 128 с. ISBN 5-7511-1501-5, глава 3 алгоритм 3.1