D.Polykovskiy: Init

2016-11-12T19:59:12Z

Init

Новая страница

{{Значения|Триангуляция}}
[[Файл:Delaunay_circumcircles_vectorial.svg|right|thumb|280px|Пример триангуляции Делоне. Из каждой точки порождается окружность, проходящая через две ближайшие в [[Евклидова метрика|метрике Евклида]] точки.]]

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

== Свойства ==

* Триангуляция Делоне взаимно однозначно соответствует [[диаграмма Вороного|диаграмме Вороного]] для того же множества точек.
* Как следствие: если никакие четыре точки не лежат на одной окружности, триангуляция Делоне единственна.
* Триангуляция Делоне максимизирует минимальный угол среди всех углов всех построенных треугольников, тем самым избегаются «тонкие» треугольники.
* Триангуляция Делоне максимизирует сумму радиусов вписанных шаров.
* Триангуляция Делоне минимизирует [[дискретный функционал Дирихле]].
* Триангуляция Делоне минимизирует максимальный радиус минимального объемлющего шара.
* Триангуляция Делоне на плоскости обладает минимальной суммой радиусов окружностей, описанных около треугольников, среди всех возможных триангуляций{{sfn|Скворцов|2002|loc=теорема 3|с=11}}.

== Алгоритм «разделяй и властвуй» ==
{{main|Алгоритм Киркпатрика}}
Данный алгоритм основан на стандартной для многих алгоритмов методике сведения сложной задачи к более простым, в которых решение очевидно. Сам алгоритм для ''N'' > 1 состоит из 2 шагов:
# Разбиение исходного множества на более мелкие множества. Для этого мы проводим вертикальные или горизонтальные прямые в середине множества и уже относительно этих прямых разделяем точки на две части примерно по ''N''/2. После для каждой группы точек рекурсивно запускаем процесс деления.
# Объединение оптимальных триангуляций. Сначала находятся две пары точек, отрезки которых образуют в совокупности с построенными триангуляциями выпуклую фигуру. Они соединяются отрезками, и один из полученных отрезков выбирается как начало для последующего обхода. Обход заключается в следующем: на этом отрезке мы как будто «надуваем пузырь» внутрь до первой точки, которую достигнет раздувающаяся окружность «пузыря». С найденной точкой соединяется та точка отрезка, которая не была с ней соединена. Полученный отрезок проверяется на пересечение с уже существующими отрезками триангуляции, и в случае пересечения они удаляются из триангуляции. После этого новый отрезок принимается за начало для нового «пузыря». Цикл повторяется до тех пор, пока начало не совпадёт со вторым отрезком выпуклой оболочки.

Сложность разбиения множества <math>O(\log N)</math>, объединения — <math>O(N)</math> для каждого объединения, итоговая сложность алгоритма — <math>O(N \log N)</math>{{sfn|Скворцов|2002|loc=глава 3, алгоритм 3.1}}.

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

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

== Применение ==

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

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

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

== Литература ==
* {{книга
|автор = Скворцов А. В.
|заглавие = Триангуляция Делоне и её применение
|город = Томск
|издательство = Изд-во Томского университета
|год = 2002
|страниц = 128
|isbn = 5-7511-1501-5
|ref = Скворцов
}}

[[Категория:Вычислительная геометрия]]
[[Категория:Комбинаторная геометрия]]
[[Категория:Геометрические алгоритмы]]

Участник:D.Polykovskiy/Триангуляция Делоне - История изменений

D.Polykovskiy: Init