Триангуляция Питтуэя - Pitteway triangulation - Wikipedia
В вычислительная геометрия, а Триангуляция Питтуэя это триангуляция набора точек в которой ближайший сосед любой точки п внутри триангуляции находится одна из вершин треугольника, содержащего п. В качестве альтернативы это Триангуляция Делоне в котором каждый внутренний край пересекает свой двойной Диаграмма Вороного край. Триангуляции Питтеэя названы в честь Майкла Питтуэя, изучившего их в 1973 году. Не каждый набор точек поддерживает триангуляцию Питтеэя. Когда такая триангуляция существует, это частный случай Триангуляция Делоне, и состоит из объединения Габриэль граф и выпуклый корпус.
История
Концепция триангуляции Питтвея была введена Питтуэй (1973). Смотрите также Маклейн (1976), который пишет: «Оптимальное разбиение - это такое, в котором для любой точки внутри любого треугольника эта точка находится по крайней мере так же близко к одной из вершин этого треугольника, как и к любой другой точке данных». Название «триангуляция Питтеэя» было дано Okabe et al. (2000).
Контрпримеры
Золото (1978) указывает на то, что не каждый набор точек поддерживает триангуляцию Питтеуэя. Например, любая триангуляция правильный пятиугольник включает центральный равнобедренный треугольник так что точка п у середины одной из сторон треугольника есть ближайший сосед вне треугольника.
Связь с другими геометрическими графиками
Когда существует триангуляция Pitteway, средняя точка каждого внутреннего ребра по отношению к триангуляции должна иметь две конечные точки ребра в качестве ближайших соседей, поскольку любой другой сосед нарушит свойство Pitteway для ближайших точек в одном из двух смежных треугольников. Таким образом, окружность, имеющая это ребро в качестве диаметра, должна быть пуста от вершин, поэтому триангуляция Питтвея состоит из Габриэль граф вместе с выпуклый корпус набора точек. И наоборот, когда граф Габриэля и выпуклая оболочка вместе образуют триангуляцию, это триангуляция Питтеэя.
Поскольку весь граф Габриэля и выпуклые ребра оболочки являются частью Триангуляция Делоне, триангуляция Питтвея, если она существует, уникальна для точек в общая позиция и совпадает с триангуляцией Делоне. Однако наборы точек без триангуляции Питтвея все равно будут иметь триангуляцию Делоне.
В триангуляции Питтеэя каждое ребро pq либо принадлежит выпуклой оболочке, либо пересекает край Диаграмма Вороного который разделяет ячейки, содержащие п и q. В некоторых ссылках это свойство используется для определения триангуляции Питтеэя как триангуляции Делоне, в которой все внутренние ребра Делоне пересекают свои двойные ребра Вороного. Однако триангуляция Pitteway может включать выпуклые края корпуса, которые не пересекают свои двойники.[1]
Примечания
Рекомендации
- Добрин, Адам (2005), Обзор свойств и разновидностей диаграмм Вороного. (PDF), Whitman College
- Голд, К. М. (1978), «Практическое создание и использование структур данных географических треугольных элементов» (PDF), в Dutton, G. (ред.), Труды Первого международного симпозиума углубленных исследований топологических структур данных для географических информационных систем. Гарвардские документы по географическим информационным системам, вып. 5 - Структуры данных: поверхностные и многомерные., Бостон: Лаборатория компьютерной графики и пространственного анализа, Гарвардский университет, стр. 1–18..
- Маклейн, Д. Х. (1976), «Двумерная интерполяция случайных данных», Компьютерный журнал, 19: 178–181, Дои:10.1093 / comjnl / 19.2.178.
- Окабе, Ацуюки; Сапоги, Барри Н .; Чиу, Сун Нок; Сугихара, Кокичи (2000), Пространственные мозаики: концепции и приложения диаграмм Вороного, Wiley.
- Питтуэй, М. Л. В. (1973), "Исследование компьютерной графики в академической среде", Datafair '73.