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

В вычислительной геометрии триангуляция Делоне или триангуляция Делоне набора точек на плоскости подразделяет их выпуклую оболочку. ^[1]на треугольники, описанные окружности которых не содержат ни одной точки. Это максимизирует размер наименьшего угла в любом из треугольников и позволяет избежать ленточных треугольников .

Триангуляция названа в честь Бориса Делоне за его работу над ней в 1934 году. ^[2]

Если все точки лежат на прямой линии, понятие триангуляции вырождается и триангуляции Делоне не существует. Для четырех и более точек одной и той же окружности (например, вершин прямоугольника) триангуляция Делоне не единственна: каждая из двух возможных триангуляций, разбивающих четырехугольник на два треугольника, удовлетворяет «условию Делоне», т. е. требованию, что описанные окружности всех треугольников имеют пустую внутреннюю часть.

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

Связь с диаграммой Вороного [ править ]

Триангуляция Делоне со всеми описанными окружностями и их центрами (красным).

Соединение центров описанных окружностей дает диаграмму Вороного (красный).

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

Особые случаи, когда эта связь не соблюдается или является двусмысленной, включают такие случаи, как:

Три или более точки, лежащие на одной прямой , где описанные окружности имеют бесконечный радиус .
Четыре или более точки идеального круга, триангуляция которого неоднозначна, а все центры описанной окружности тривиально идентичны.
Ребра диаграммы Вороного, уходящие на бесконечность, не определяются этим соотношением в случае конечного множества $P$ . Делоне Если триангуляция рассчитывается с использованием алгоритма Бойера – Ватсона , то следует игнорировать центры описанных треугольников, имеющих общую вершину с «супертреугольником». Ребра, уходящие в бесконечность, начинаются от центра описанной окружности и перпендикулярны общему краю сохраняемого и игнорируемого треугольника.

d -мерный Делоне [ править ]

Для набора $P$ точек в ( $d$ -мерном) евклидовом пространстве — триангуляция Делоне это триангуляция $DT(P)$ такая, что ни одна точка в $P$ не находится внутри описанной гиперсферы любого $d$ - симплекса в $DT(P)$ . Известно ^[2]что существует единственная триангуляция Делоне для $P$ , если $P$ — множество точек общего положения ; то есть аффинная оболочка $P$ является $d$ -мерной, и ни один набор из $d + 2$ точек в $P$ не лежит на границе шара, внутренняя часть которого не пересекает $P$ .

Задачу нахождения триангуляции Делоне множества точек в $d$ -мерном евклидовом пространстве можно преобразовать в задачу нахождения выпуклой оболочки множества точек в ( $d +1$ )-мерном пространстве. Это можно сделать, присвоив каждой точке $p$ дополнительную координату, равную $| р | 2$ , превратив его таким образом в гиперпараболоид (это называется «подъемом»); берем нижнюю сторону выпуклой оболочки (поскольку верхняя торцевая крышка обращена вверх от начала координат и должна быть отброшена); и отображение обратно в $d$ -мерное пространство путем удаления последней координаты. Поскольку выпуклая оболочка уникальна, то и триангуляция уникальна, если предположить, что все грани выпуклой оболочки являются симплексами . Несимплициальные фасеты возникают только тогда, когда $d + 2$ исходных точки лежат на одной и той же $d$ - гиперсфере , т. е. точки не находятся в общем положении. ^[3]

Свойства [ править ]

Пусть $n$ — количество точек, а $d —$ количество измерений.

Объединение всех симплексов триангуляции представляет собой выпуклую оболочку точек.
Триангуляция Делоне содержит $\textstyle O{\bigl (}n^{\lceil d/2\rceil }{\bigr )}$ простой ^[4]
В плоскости ( $d = 2$ ), если на выпуклой оболочке имеется $b$ вершин, то любая триангуляция точек имеет не более $2 n - 2 - b$ треугольников плюс одну внешнюю грань (см. Эйлерову характеристику ).
Если точки распределены по процессу Пуассона на плоскости с постоянной интенсивностью, то каждую вершину окружают в среднем шесть треугольников. В более общем смысле для одного и того же процесса в $измерениях d$ среднее количество соседей является константой, зависящей только от $d$ . ^[5]
На плоскости триангуляция Делоне максимизирует минимальный угол. По сравнению с любой другой триангуляцией точек наименьший угол в триангуляции Делоне по крайней мере такой же большой, как и наименьший угол в любой другой. Однако триангуляция Делоне не обязательно минимизирует максимальный угол. ^[6] Триангуляция Делоне также не обязательно минимизирует длину ребер.
Окружность, описывающая любой треугольник Делоне, не содержит внутри себя никаких других входных точек.
Если окружность, проходящая через две входные точки, не содержит внутри себя других входных точек, то отрезок, соединяющий две точки, является ребром триангуляции Делоне данных точек.
Каждый треугольник триангуляции Делоне набора точек в $d$ -мерном пространстве соответствует грани выпуклой оболочки проекции точек на ( $d + 1$ )-мерный параболоид , и наоборот.
Ближайший сосед $b$ к любой точке $p$ находится на ребре $bp$ в триангуляции Делоне, поскольку граф ближайших соседей является подграфом триангуляции Делоне.
Триангуляция Делоне представляет собой геометрический гаечный ключ : известно, что на плоскости ( $d = 2$ ) кратчайший путь между двумя вершинами вдоль ребер Делоне не превышает евклидово расстояние между ними более чем в 1,998 раза. ^[7]

Определение Визуального Делоне: Переворачивание [ править ]

Из приведенных выше свойств вытекает важная особенность: если рассматривать два треугольника $△ ABD, △ BCD$ с общим ребром $BD$ (см. рисунки), то если сумма углов $α + γ \leq 180°$ , треугольники удовлетворяют условию Делоне.

Это важное свойство, поскольку оно позволяет использовать технику переворота . Если два треугольника не удовлетворяют условию Делоне, замена общего ребра $BD$ на общее ребро $AC$ дает два треугольника, которые удовлетворяют условию Делоне:

Эта триангуляция не удовлетворяет условию Делоне (сумма $α$ и $γ$ больше 180°).
Эта пара треугольников не удовлетворяет условию Делоне (есть точка внутри описанной окружности).
Переворот общего ребра дает действительную триангуляцию Делоне для четырех точек.

Эта операция называется переворотом и может быть обобщена на три и более измерений. ^[8]

Алгоритмы [ править ]

Многие алгоритмы вычисления триангуляции Делоне основаны на быстрых операциях определения того, находится ли точка внутри описанной окружности треугольника, а также на эффективной структуре данных для хранения треугольников и ребер. В двух измерениях один из способов определить, находится ли точка $D$ в описанной окружности $A, B, C,$ — это вычислить определитель : ^[9]

{\begin{aligned}&{\begin{vmatrix}A_{x}&A_{y}&A_{x}^{2}+A_{y}^{2}&1\\B_{x}&B_{y}&B_{x}^{2}+B_{y}^{2}&1\\C_{x}&C_{y}&C_{x}^{2}+C_{y}^{2}&1\\D_{x}&D_{y}&D_{x}^{2}+D_{y}^{2}&1\end{vmatrix}}\\[8pt]={}&{\begin{vmatrix}A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}-D_{x})^{2}+(A_{y}-D_{y})^{2}\\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}-D_{x})^{2}+(B_{y}-D_{y})^{2}\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}-D_{x})^{2}+(C_{y}-D_{y})^{2}\end{vmatrix}}>0\end{aligned}}

Когда $A, B, C$ отсортированы в порядке против часовой стрелки , этот определитель положителен, только если $D$ лежит внутри описанной окружности.

Алгоритмы переворота [ править ]

Как упоминалось выше, если треугольник не Делоне, мы можем перевернуть одно из его ребер. Это приводит к простому алгоритму: построить любую триангуляцию точек, а затем переворачивать ребра до тех пор, пока ни один треугольник не будет не треугольником Делоне. К сожалению, для этого может потребоваться $Ω(n 2)$ переворачивание края. ^[10] Хотя этот алгоритм можно обобщить на три и более измерений, его сходимость в этих случаях не гарантируется, поскольку она обусловлена связностью основного флип-графа : этот граф связен для двумерных наборов точек, но может быть отключен. в более высоких измерениях. ^[8]

Инкрементальный [ править ]

Самый простой способ эффективного вычисления триангуляции Делоне — многократно добавлять по одной вершине за раз, перетриангулируя затронутые части графа. Когда добавляется вершина $v$ , мы разбиваем треугольник, содержащий $вершину v$ , на три , а затем применяем алгоритм переворота. Если сделать это по-наивному, это займет $время O(n)$ : мы просматриваем все треугольники, чтобы найти тот, который содержит $v$ , затем мы потенциально переворачиваем каждый треугольник. Тогда общее время выполнения составит $O(n 2)$ .

Если мы вставим вершины в случайном порядке, то окажется (путем довольно сложного доказательства), что каждая вставка перевернет в среднем только $O(1)$ треугольников – хотя иногда она перевернет гораздо больше треугольников. ^[11]Это все еще оставляет время для улучшения местоположения точки. Мы можем хранить историю выполненных разбиений и переворотов: каждый треугольник хранит указатель на два или три треугольника, которые его заменили. Чтобы найти треугольник, содержащий $v$ , мы начинаем с корневого треугольника и следуем за указателем, указывающим на треугольник, содержащий $v$ , пока не найдем треугольник, который еще не был заменен. В среднем это также займет $время O(log n)$ . Таким образом, для всех вершин это занимает $время O(n log n)$ . ^[12] Хотя эта техника распространяется и на более высокие измерения (как доказали Эдельсбруннер и Шах ^[13]), время выполнения может быть экспоненциальным в измерении, даже если окончательная триангуляция Делоне мала.

Алгоритм Бойера-Ватсона предлагает еще один подход к поэтапному построению. Это дает альтернативу перевороту ребер для вычисления треугольников Делоне, содержащих новую вставленную вершину.

К сожалению, алгоритмы, основанные на переворотах, обычно трудно распараллелить, поскольку добавление некоторой определенной точки (например, центральной точки колеса телеги) может привести к $O(n)$ последовательным переворотам. Блеллох и др. ^[14] предложил другую версию инкрементного алгоритма, основанную на rip-and-tent, которая практична и хорошо распараллелена с полилогарифмическим интервалом .

Разделяй и властвуй [ править ]

Алгоритм « разделяй и властвуй» для двумерной триангуляции был разработан Ли и Шахтером и улучшен Гибасом и Столфи. ^[9]^[15] и позже Дуайером. ^[16]В этом алгоритме рекурсивно рисуется линия, разделяющая вершины на два набора. Триангуляция Делоне вычисляется для каждого набора, а затем два набора объединяются вдоль линии разделения. Используя некоторые хитрости, операцию слияния можно выполнить за время $O(n)$ , поэтому общее время выполнения составит $O(n log n)$ . ^[17]

Для определенных типов наборов точек, таких как равномерное случайное распределение, путем разумного выбора линий разделения ожидаемое время может быть уменьшено до $O(n log log n)$ , сохраняя при этом производительность в худшем случае.

Парадигма «разделяй и властвуй» для выполнения триангуляции в $измерениях d$ представлена в документе «DeWall: быстрый алгоритм триангуляции Делоне в формате «разделяй и властвуй» в E. ^д» П. Чиньони, К. Монтани, Р. Скопиньо. ^[18]

Было показано, что алгоритм «разделяй и властвуй» является самым быстрым методом последовательной генерации DT. ^[19]^[20]

Свипхалл [ править ]

Свипхалл ^[21]представляет собой гибридный метод двумерной триангуляции Делоне, в котором используется радиально распространяющаяся оболочка и алгоритм переворота. Оболочка развертки создается последовательно путем итерации радиально отсортированного набора 2D-точек и соединения треугольников с видимой частью выпуклой оболочки, что дает неперекрывающуюся триангуляцию. Таким способом можно построить выпуклую оболочку, если порядок точек гарантирует, что ни одна точка не попадет в треугольник. Но радиальная сортировка должна свести к минимуму переворачивание, поскольку изначально требует высокой степени Делоне. Затем это сочетается с заключительным итеративным шагом переворота треугольника.

Приложения [ править ]

Евклидово минимальное остовное дерево набора точек является подмножеством триангуляции Делоне тех же точек, ^[22] и это можно использовать для эффективного вычисления.

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

Триангуляции Делоне можно использовать для определения плотности или интенсивности выборок точек с помощью средства оценки поля тесселяции Делоне (DTFE) .

Триангуляции Делоне часто используются для создания сеток для решателей с дискретизацией по пространству, таких как метод конечных элементов и метод конечных объемов физического моделирования, из-за гарантии угла и потому, что были разработаны быстрые алгоритмы триангуляции. Обычно область построения сетки задается как грубый симплициальный комплекс ; чтобы сетка была численно стабильной, ее необходимо уточнить, например, с помощью алгоритма Руперта .

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

Ограниченная триангуляция Делоне нашла применение при планировании пути , автоматизированном вождении и топографической съемке. ^[23]

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

Бета-скелет
Центроидальная мозаика Вороного
Алгоритмы выпуклой оболочки
Уточнение Делоне
Набор Делоне - также известный как набор Делоне.
Нарушенная гипероднородность
Самый дальний обход – инкрементная вставка Вороного
График Габриэля
Дорога Гигантов
Анализ градиентных паттернов
Граница Хэмминга – граница упаковки сфер
Алгоритм Линде – Дайвера – Грея
Алгоритм Ллойда – итерация Вороного
Набор Мейера
Число Писо – Виджаярагавана
Триангуляция Питтвея
Плесоэдр
Квазикристалл
Квазитриангуляция
Салемский номер
Точка Штейнера (треугольник)
Треугольная сетка
Граф Уркарта
Диаграмма Вороного

Ссылки [ править ]

^ Грубо говоря, это будет область, натянутая вокруг точек резинкой.
^ Перейти обратно: ^а ^б Делоне, Борис (1934). «На пустой сфере» . Вестник Академии наук СССР, класс математических и естественных наук (на французском языке). 6 :793–800.
^ Фукуда, Комэй . «Часто задаваемые вопросы по многогранным вычислениям» . www.cs.mcgill.ca . Проверено 29 октября 2018 г.
^ Зайдель, Раймунд (1995). «Теорема о верхней оценке многогранников: простое доказательство ее асимптотической версии». Вычислительная геометрия . 5 (2): 115–116. дои : 10.1016/0925-7721(95)00013-Y .
^ Мейеринг, Дж. Л. (1953). «Площадь границы раздела, длина ребра и количество вершин в кристаллических агрегатах со случайным зародышеобразованием» (PDF) . Отчеты об исследованиях Philips . 8 : 270–290. Архивировано из оригинала (PDF) 8 марта 2017 г. Как цитирует Дуайер, Рекс А. (1991). «Многомерные диаграммы Вороного в линейное ожидаемое время». Дискретная и вычислительная геометрия . 6 (4): 343–367. дои : 10.1007/BF02574694 . МР 1098813 .
^ Эдельсбруннер, Герберт ; Тан, Тиоу Сенг; Ваупотич, Роман (1992). «Ан О ( н ² log n ) алгоритм времени для триангуляции угла minmax» (PDF) . SIAM Journal on Scientific and Statistical Computing . 13 (4): 994–1008. CiteSeerX 10.1.1.66.2895 . doi : 10.1137/0913058 . MR 1166172. Архивировано из оригинал (PDF) 9 февраля 2017 г. Проверено 24 октября 2017 . г.
^ Ся, Гэ (2013). «Коэффициент растяжения триангуляции Делоне меньше 1,998». SIAM Journal по вычислительной технике . 42 (4): 1620–1659. arXiv : 1103.4361 . дои : 10.1137/110832458 . МР 3082502 . S2CID 6646528 .
^ Перейти обратно: ^а ^б Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010). Триангуляции, структуры для алгоритмов и приложений . Алгоритмы и вычисления в математике. Том. 25. Спрингер.
^ Перейти обратно: ^а ^б Гибас, Леонидас ; Столфи, Хорхе (1985). «Примитивы для манипуляций с генеральными подразделениями и вычисления Вороного» . Транзакции ACM с графикой . 4 (2): 74–123. дои : 10.1145/282918.282923 . S2CID 52852815 .
^ Уртадо, Ф .; Ной, М.; Уррутия, Дж. (1999). «Переворачивание ребер в триангуляциях» . Дискретная и вычислительная геометрия . 22 (3): 333–346. дои : 10.1007/PL00009464 .
^ Гибас, Леонидас Дж .; Кнут, Дональд Э .; Шарир, Миша (1992). «Рандомизированное пошаговое построение диаграмм Делоне и Вороного». Алгоритмика . 7 (1–6): 381–413. дои : 10.1007/BF01758770 . S2CID 3770886 .
^ де Берг, Марк; Отфрид Чеонг ; Марк ван Кревелд; Марк Овермарс (2008). Вычислительная геометрия: алгоритмы и приложения (PDF) . Издательство Спрингер. ISBN 978-3-540-77973-5 . Архивировано из оригинала (PDF) 28 октября 2009 г. Проверено 23 февраля 2010 г.
^ Эдельсбруннер, Герберт ; Шах, Нимиш (1996). «Пошаговые топологические перевороты для регулярных триангуляций». Алгоритмика . 15 (3): 223–241. дои : 10.1007/BF01975867 . S2CID 12976796 .
^ Блеллох, Гай; Гу, Ян; Шун, Джулиан; и Сун, Ихан. Параллелизм в рандомизированных инкрементных алгоритмах. Архивировано 25 апреля 2018 г. в Wayback Machine . SPAA 2016. doi:10.1145/2935764.2935766.
^ Петерсон, Сэмюэл. «РАСЧЕТ ОГРАНИЧЕННЫХ ТРИАНГУЛЯЦИЙ ДЕЛОНЕ НА ПЛОСКОСТИ» . www.geom.uiuc.edu . Архивировано из оригинала 22 сентября 2017 года . Проверено 25 апреля 2018 г.
^ Дуайер, Рекс А. (ноябрь 1987 г.). «Более быстрый алгоритм «разделяй и властвуй» для построения триангуляций Делоне». Алгоритмика . 2 (1–4): 137–151. дои : 10.1007/BF01840356 . S2CID 10828441 .
^ Лич, Г. (июнь 1992 г.). «Улучшение оптимальных алгоритмов триангуляции Делоне для наихудшего случая». 4-я Канадская конференция по вычислительной геометрии . CiteSeerX 10.1.1.56.2323 .
^ Чиньони, П.; К. Монтани; Р. Скопиньо (1998). «DeWall: быстрый алгоритм триангуляции Делоне «разделяй и властвуй» в E ^д". Компьютерное проектирование . 30 (5): 333–341. doi : 10.1016/S0010-4485(97)00082-1 .
^ Сравнение последовательных алгоритмов триангуляции Делоне «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 8 марта 2012 г. Проверено 18 августа 2010 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
^ «Алгоритмы триангуляции и структуры данных» . www.cs.cmu.edu . Архивировано из оригинала 10 октября 2017 года . Проверено 25 апреля 2018 г.
^ "S-hull" (PDF). s-hull.org. Archived (PDF) from the original on 2013-10-27. Retrieved 25 April 2018.
^ Франц Ауренхаммер; Рольф Кляйн; Дер-цай Ли (26 июня 2013 г.). Диаграммы Вороного и триангуляции Делоне . Мировое научное издательство. стр. 197–. ISBN 978-981-4447-65-2 .
^ Стерлинг Дж. Андерсон; Сисир Б. Каруманчи; Карл Ягнемма (5 июля 2012 г.). «Планирование и контроль на основе ограничений для безопасной полуавтономной эксплуатации транспортных средств» (PDF) . Симпозиум IEEE по интеллектуальным транспортным средствам 2012 г. IEEE. дои : 10.1109/IVS.2012.6232153 . Архивировано из оригинала (PDF) 28 февраля 2019 года . Проверено 27 февраля 2019 г.

Внешние ссылки [ править ]

Триангуляция Делоне в CGAL , Библиотеке алгоритмов вычислительной геометрии:
- Мариэтт Ивинек . 2D триангуляция . Проверено в апреле 2010 г.
- Пион, Сильвен; Тейо, Моник . 3D триангуляции . Проверено в апреле 2010 г.
- Хорнус, Самуэль; Девиллерс, Оливье; Джамин, Клемент. dD Триангуляции .
- Херт, Сьюзен; Сил, Майкл. dD Выпуклые оболочки и триангуляции Делоне . Проверено в апреле 2010 г.
Poly2Tri : Инкрементная триангуляция Делоне с ограничениями . Реализация C++ с открытым исходным кодом. Получено в апреле 2019 г.
« Разделяй и властвуй», построение триангуляции Делоне . Реализация C99 с открытым исходным кодом. Получено в апреле 2019 г.
« CDT: Ограниченная триангуляция Делоне в C++ ». Реализация C++ с открытым исходным кодом. Проверено в августе 2022 года.

[1] Грубо говоря, это будет область, натянутая вокруг точек резинкой.

[Delaunay1934-2] Перейти обратно: ^а ^б Делоне, Борис (1934). «На пустой сфере» . Вестник Академии наук СССР, класс математических и естественных наук (на французском языке). 6 :793–800.

[Fukuda-3] Фукуда, Комэй . «Часто задаваемые вопросы по многогранным вычислениям» . www.cs.mcgill.ca . Проверено 29 октября 2018 г.

[Seidel1995-4] Зайдель, Раймунд (1995). «Теорема о верхней оценке многогранников: простое доказательство ее асимптотической версии». Вычислительная геометрия . 5 (2): 115–116. дои : 10.1016/0925-7721(95)00013-Y .

[Meijering-5] Мейеринг, Дж. Л. (1953). «Площадь границы раздела, длина ребра и количество вершин в кристаллических агрегатах со случайным зародышеобразованием» (PDF) . Отчеты об исследованиях Philips . 8 : 270–290. Архивировано из оригинала (PDF) 8 марта 2017 г. Как цитирует Дуайер, Рекс А. (1991). «Многомерные диаграммы Вороного в линейное ожидаемое время». Дискретная и вычислительная геометрия . 6 (4): 343–367. дои : 10.1007/BF02574694 . МР 1098813 .

[ETW1992-6] Эдельсбруннер, Герберт ; Тан, Тиоу Сенг; Ваупотич, Роман (1992). «Ан О ( н ² log n ) алгоритм времени для триангуляции угла minmax» (PDF) . SIAM Journal on Scientific and Statistical Computing . 13 (4): 994–1008. CiteSeerX 10.1.1.66.2895 . doi : 10.1137/0913058 . MR 1166172. Архивировано из оригинал (PDF) 9 февраля 2017 г. Проверено 24 октября 2017 . г.

[Xia-7] Ся, Гэ (2013). «Коэффициент растяжения триангуляции Делоне меньше 1,998». SIAM Journal по вычислительной технике . 42 (4): 1620–1659. arXiv : 1103.4361 . дои : 10.1137/110832458 . МР 3082502 . S2CID 6646528 .

[DRS-8] Перейти обратно: ^а ^б Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010). Триангуляции, структуры для алгоритмов и приложений . Алгоритмы и вычисления в математике. Том. 25. Спрингер.

[GS1985-9] Перейти обратно: ^а ^б Гибас, Леонидас ; Столфи, Хорхе (1985). «Примитивы для манипуляций с генеральными подразделениями и вычисления Вороного» . Транзакции ACM с графикой . 4 (2): 74–123. дои : 10.1145/282918.282923 . S2CID 52852815 .

[Hurtado-10] Уртадо, Ф .; Ной, М.; Уррутия, Дж. (1999). «Переворачивание ребер в триангуляциях» . Дискретная и вычислительная геометрия . 22 (3): 333–346. дои : 10.1007/PL00009464 .

[GKS1992-11] Гибас, Леонидас Дж .; Кнут, Дональд Э .; Шарир, Миша (1992). «Рандомизированное пошаговое построение диаграмм Делоне и Вороного». Алгоритмика . 7 (1–6): 381–413. дои : 10.1007/BF01758770 . S2CID 3770886 .

[deBerg-12] де Берг, Марк; Отфрид Чеонг ; Марк ван Кревелд; Марк Овермарс (2008). Вычислительная геометрия: алгоритмы и приложения (PDF) . Издательство Спрингер. ISBN 978-3-540-77973-5 . Архивировано из оригинала (PDF) 28 октября 2009 г. Проверено 23 февраля 2010 г.

[ES1996-13] Эдельсбруннер, Герберт ; Шах, Нимиш (1996). «Пошаговые топологические перевороты для регулярных триангуляций». Алгоритмика . 15 (3): 223–241. дои : 10.1007/BF01975867 . S2CID 12976796 .

[Parallel-14] Блеллох, Гай; Гу, Ян; Шун, Джулиан; и Сун, Ихан. Параллелизм в рандомизированных инкрементных алгоритмах. Архивировано 25 апреля 2018 г. в Wayback Machine . SPAA 2016. doi:10.1145/2935764.2935766.

[Peterson-15] Петерсон, Сэмюэл. «РАСЧЕТ ОГРАНИЧЕННЫХ ТРИАНГУЛЯЦИЙ ДЕЛОНЕ НА ПЛОСКОСТИ» . www.geom.uiuc.edu . Архивировано из оригинала 22 сентября 2017 года . Проверено 25 апреля 2018 г.

[Dwyer1987-16] Дуайер, Рекс А. (ноябрь 1987 г.). «Более быстрый алгоритм «разделяй и властвуй» для построения триангуляций Делоне». Алгоритмика . 2 (1–4): 137–151. дои : 10.1007/BF01840356 . S2CID 10828441 .

[Leach1992-17] Лич, Г. (июнь 1992 г.). «Улучшение оптимальных алгоритмов триангуляции Делоне для наихудшего случая». 4-я Канадская конференция по вычислительной геометрии . CiteSeerX 10.1.1.56.2323 .

[CMS1998-18] Чиньони, П.; К. Монтани; Р. Скопиньо (1998). «DeWall: быстрый алгоритм триангуляции Делоне «разделяй и властвуй» в E ^д". Компьютерное проектирование . 30 (5): 333–341. doi : 10.1016/S0010-4485(97)00082-1 .

[19] Сравнение последовательных алгоритмов триангуляции Делоне «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 8 марта 2012 г. Проверено 18 августа 2010 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[20] «Алгоритмы триангуляции и структуры данных» . www.cs.cmu.edu . Архивировано из оригинала 10 октября 2017 года . Проверено 25 апреля 2018 г.

[21] "S-hull" (PDF). s-hull.org. Archived (PDF) from the original on 2013-10-27. Retrieved 25 April 2018.

[AK2013-22] Франц Ауренхаммер; Рольф Кляйн; Дер-цай Ли (26 июня 2013 г.). Диаграммы Вороного и триангуляции Делоне . Мировое научное издательство. стр. 197–. ISBN 978-981-4447-65-2 .

[AKI2012-23] Стерлинг Дж. Андерсон; Сисир Б. Каруманчи; Карл Ягнемма (5 июля 2012 г.). «Планирование и контроль на основе ограничений для безопасной полуавтономной эксплуатации транспортных средств» (PDF) . Симпозиум IEEE по интеллектуальным транспортным средствам 2012 г. IEEE. дои : 10.1109/IVS.2012.6232153 . Архивировано из оригинала (PDF) 28 февраля 2019 года . Проверено 27 февраля 2019 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]