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

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

В математике и вычислительной геометрии , A триангуляции Делоне (также известный как триангуляции Делоне ) для данного множества P из дискретных точек на плоскости является триангуляция ДТ ( Р ) так , что ни одна точка в P не находится внутри окружности любого треугольника в DT ( P ). Триангуляции Делоне максимизируют минимальный угол всех углов треугольников в триангуляции; они стараются избегать полосатых треугольников . Триангуляция названа в честь Бориса Делоне.за работу по этой теме с 1934 г. ^[1]

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

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

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

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

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

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

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

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

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

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

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

Примеры шагов

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

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

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

Определение Visual Delaunay: переворачивание [ править ]

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

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

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

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

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

Нам нужен надежный и быстрый способ определить, лежит ли точка D в описанной окружности A , B , C.

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

{\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}}={\begin{vmatrix}A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}^{2}-D_{x}^{2})+(A_{y}^{2}-D_{y}^{2})\\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}^{2}-D_{x}^{2})+(B_{y}^{2}-D_{y}^{2})\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}^{2}-D_{x}^{2})+(C_{y}^{2}-D_{y}^{2})\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 ² ). ^[9] Хотя этот алгоритм может быть обобщен для трех и более измерений, его сходимость в этих случаях не гарантируется, поскольку она обусловлена связностью лежащего в основе флип-графа : этот граф связан для двумерных наборов точек, но может быть отключенным в более высоких измерениях. ^[7]

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

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

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

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

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

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

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

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

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

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

Суифалл [ править ]

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

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

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

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

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

Триангуляция Делоне случайного набора из 100 точек на плоскости.

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

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

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

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

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

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

^ a b Делоне, Борис (1934). "Sur la sphère vide" . Bulletin de l'Académie des Sciences de l'URSS, Classe des Sciences Mathématiques et Naturelles . 6 : 793–800.
↑ Фукуда, Комей. «Часто задаваемые вопросы в вычислениях многогранников» . www.cs.mcgill.ca . Проверено 29 октября 2018 года .
Перейти ↑ Seidel, Raimund (1995). «Теорема о верхней границе для многогранников: простое доказательство ее асимптотической версии». Вычислительная геометрия . 5 (2): 115–116. DOI : 10.1016 / 0925-7721 (95) 00013-Y .
^ Мейеринг, JL (1953), «Площадь границы раздела, длина ребра и количество вершин в кристаллических агрегатах со случайным зарождением» (PDF) , Philips Research Reports , 8 : 270–290, заархивировано из оригинала (PDF) на 2017- 03-08 . Как указано на Dwyer, Рекс А. (1991), "Многомерные диаграммы Вороного в линейной ожидаемого времени", дискретных и вычислительной геометрии , 6 (4): 343-367, DOI : 10.1007 / BF02574694 , МР 1098813 .
^ Эдельсбруннер, Герберт ; Тан, Тиоу Сенг; Ваупотич, Роман (1992), " Временной алгоритм O ( n 2 log n ) для минимальной угловой триангуляции" (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) на 2017-02-09 , извлекаются 2017-10-24 .
^ Ся, Ge (2011), "перегон фактор триангуляционных меньше , чем 1,998", Computing Research Repository - КОРР , 42 , DOI : 10,1137 / 110832458.
^ а б Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010). Триангуляции, структуры для алгоритмов и приложений . Алгоритмы и вычисления в математике. 25 . Springer.
^ Guibas Леонидас ; Столфи, Хорхе (1985). «Примитивы для манипулирования общими подразделениями и вычисления Вороного». Транзакции ACM на графике . 4 (2): 74–123. DOI : 10.1145 / 282918.282923 . S2CID 52852815 .
^ Уртадо, Ф .; М. Ной; Дж. Уррутия (1999). «Перевернутые грани в триангуляции» . Дискретная и вычислительная геометрия . 22 (3): 333–346. DOI : 10.1007 / PL00009464 .
^ Гибас, Леонидас Дж .; Кнут, Дональд Э .; Шарир, Миха (1992). «Рандомизированное пошаговое построение диаграмм Делоне и Вороного». Алгоритмика . 7 (1–6): 381–413. DOI : 10.1007 / BF01758770 . S2CID 3770886 .
^ де Берг, Марк; Отфрид Чеонг ; Марк ван Кревельд; Марк Овермарс (2008). Вычислительная геометрия: алгоритмы и приложения (PDF) . Springer-Verlag. ISBN 978-3-540-77973-5. Архивировано из оригинального (PDF) 28 октября 2009 года . Проверено 23 февраля 2010 .
^ Эдельсбруннер, Герберт ; Шах, Нимиш (1996). «Инкрементальные топологические перевернутые работы для регулярных триангуляций» . Алгоритмика . 15 (3): 223–241. DOI : 10.1007 / BF01975867 . S2CID 12976796 . ^{[ мертвая ссылка ]}
^ Blelloch, Гай; Гу, Ян; Шун, Джулиан; и Сун, Ихан. Параллелизм в рандомизированных инкрементальных алгоритмах. Архивировано 25 апреля 2018 г. в Wayback Machine . SPAA 2016. DOI: 10.1145 / 2935764.2935766.
^ Guibas Леонидас; Столфи, Хорхе (апрель 1985 г.). «Примитивы для манипулирования общими подразделениями и вычисления Вороного». Транзакции ACM на графике . 4 (2): 74–123. DOI : 10.1145 / 282918.282923 .
^ "ВЫЧИСЛЕНИЕ ОГРАНИЧЕННЫХ ТРЕУГОЛЬНИКОВ ДЕЛОНЕ НА ПЛОСКОСТИ" . www.geom.uiuc.edu . Архивировано из оригинального 22 сентября 2017 года . Проверено 25 апреля 2018 года .
Перейти ↑ Dwyer, Rex A. (ноябрь 1987 г.). «Более быстрый алгоритм« разделяй и властвуй »для построения триангуляций Делоне». Алгоритмика . 2 (1–4): 137–151. DOI : 10.1007 / BF01840356 .
Перейти ↑ Leach, G. (июнь 1992 г.). « Улучшение оптимальных алгоритмов триангуляции Делоне в наихудшем случае »: 15. CiteSeerX 10.1.1.56.2323 . Cite journal requires |journal= (help)
^ Cignoni, P .; К. Монтани; Р. Скопиньо (1998). «ДеУолл: быстрый алгоритм триангуляции Делоне« разделяй и властвуй »в E ^d ». Компьютерный дизайн . 30 (5): 333–341. DOI : 10.1016 / S0010-4485 (97) 00082-1 .
^ Сравнение последовательных алгоритмов триангуляции Делоне «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 08 марта 2012 года . Проверено 18 августа 2010 . CS1 maint: archived copy as title (link)
^ «Алгоритмы триангуляции и структуры данных» . www.cs.cmu.edu . Архивировано 10 октября 2017 года . Проверено 25 апреля 2018 года .
^ "S-корпус" (PDF) . s-hull.org . Проверено 25 апреля 2018 года .
^ Франц Ауренхаммер; Рольф Кляйн; Дер-цай Ли (26 июня 2013 г.). Диаграммы Вороного и триангуляции Делоне . Мировая научная издательская компания. С. 197–. ISBN 978-981-4447-65-2.
^ Стерлинг Дж. Андерсон; Сисир Б. Каруманчи; Карл Ягнемма (5 июля 2012 г.). «Планирование и контроль на основе ограничений для безопасной, полуавтономной работы транспортных средств» (PDF) . 2012 IEEE Интеллектуальные Транспортные средства Symposium . IEEE. DOI : 10.1109 / IVS.2012.6232153 .

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

« Триангуляция Делоне ». Wolfram MathWorld. Проверено апрелем 2010 года.

Программное обеспечение [ править ]

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

[Delaunay1934-1] Делоне, Борис (1934). "Sur la sphère vide" . Bulletin de l'Académie des Sciences de l'URSS, Classe des Sciences Mathématiques et Naturelles . 6 : 793–800.

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

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

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

[5] Эдельсбруннер, Герберт ; Тан, Тиоу Сенг; Ваупотич, Роман (1992), " Временной алгоритм O ( n 2 log n ) для минимальной угловой триангуляции" (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) на 2017-02-09 , извлекаются 2017-10-24 .

[6] Ся, Ge (2011), "перегон фактор триангуляционных меньше , чем 1,998", Computing Research Repository - КОРР , 42 , DOI : 10,1137 / 110832458.

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

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

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

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

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

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

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

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

[15] "ВЫЧИСЛЕНИЕ ОГРАНИЧЕННЫХ ТРЕУГОЛЬНИКОВ ДЕЛОНЕ НА ПЛОСКОСТИ" . www.geom.uiuc.edu . Архивировано из оригинального 22 сентября 2017 года . Проверено 25 апреля 2018 года .

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

[Leach1992-17] Перейти ↑ Leach, G. (июнь 1992 г.). « Улучшение оптимальных алгоритмов триангуляции Делоне в наихудшем случае »: 15. CiteSeerX 10.1.1.56.2323 . Cite journal requires |journal= (help)

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

[19] Сравнение последовательных алгоритмов триангуляции Делоне «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 08 марта 2012 года . Проверено 18 августа 2010 . CS1 maint: archived copy as title (link)

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

[21] "S-корпус" (PDF) . s-hull.org . Проверено 25 апреля 2018 года .

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

[23] Стерлинг Дж. Андерсон; Сисир Б. Каруманчи; Карл Ягнемма (5 июля 2012 г.). «Планирование и контроль на основе ограничений для безопасной, полуавтономной работы транспортных средств» (PDF) . 2012 IEEE Интеллектуальные Транспортные средства Symposium . IEEE. DOI : 10.1109 / IVS.2012.6232153 .

[1]