Триангуляция Питтвея

В вычислительной геометрии триангуляция Питтвея — это триангуляция множества точек , в которой ближайший сосед любой точки p внутри триангуляции является одной из вершин треугольника, содержащего p .Альтернативно, это триангуляция Делоне , в которой каждое внутреннее ребро пересекает свое двойное ребро диаграммы Вороного . Триангуляции Питтвея названы в честь Майкла Питтуэя, который изучал их в 1973 году. Не каждый набор точек поддерживает триангуляцию Питтвея. Когда такая триангуляция существует, она является частным случаем триангуляции Делоне и состоит из объединения графа Габриэля и выпуклой оболочки .

История

Понятие триангуляции Питтуэя было введено Питтуэем (1973) . См. также Маклейн (1976) , который пишет: «Оптимальное разделениетакое, в котором для любой точки внутри любого треугольника эта точка лежит не менеетак близко к одной из вершин этого треугольника, как к любой другой точке данных». Название «триангуляция Питтвея» было дано Окабе и др. (2000) .

Контрпримеры

Голд (1978) указывает, что не каждый набор точек поддерживает триангуляцию Питтвея. Например, любая триангуляция правильного пятиугольника включает в себя центральный равнобедренный треугольник, такой что точка p вблизи середины одной из сторон треугольника имеет ближайшего соседа вне треугольника.

Связь с другими геометрическими графами

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

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

В триангуляции Питтвея каждое ребро pq либо принадлежит выпуклой оболочке, либо пересекает ребро диаграммы Вороного , разделяющей ячейки, содержащие p и q . В некоторых ссылках это свойство используется для определения триангуляции Питтвея как триангуляции Делоне, в которой все внутренние ребра Делоне пересекают свои двойственные ребра Вороного. Однако триангуляция Питтвея может включать в себя выпуклые ребра оболочки, которые не пересекают свои двойники. ^[1]

Примечания

^ Окабе и др. (2000) ; Добрин (2005) .

Ссылки

Добрин, Адам (2005), Обзор свойств и вариаций диаграмм Вороного (PDF) , Колледж Уитмена

Голд, К.М. (1978), «Практическое создание и использование структур данных географических треугольных элементов» (PDF) , в Даттоне, Г. (ред.), Труды Первого международного симпозиума по перспективным исследованиям топологических структур данных для географических информационных систем. Гарвардские документы по географическим информационным системам, том. 5 — Структуры данных: поверхностные и многомерные. , Бостон: Лаборатория компьютерной графики и пространственного анализа, Гарвардский университет, стр. 1–18 .

Маклейн, Д.Х. (1976), «Двумерная интерполяция на основе случайных данных», The Computer Journal , 19 (2): 178–181, doi : 10.1093/comjnl/19.2.178 .

Окабе, Ацуюки; Бутс, Барри Н.; Чиу, Сунг Нок; Сугихара, Кокичи (2000), Пространственные замощения: концепции и приложения диаграмм Вороного , Уайли .

Питтуэй, MLV (1973), «Исследования компьютерной графики в академической среде», Datafair '73 .

[1] Окабе и др. (2000) ; Добрин (2005) .

[1]