В вычислительной геометрии и геометрической теории графов , A β остов или бета - скелет представляет собой неориентированный граф определяется из множества точек в евклидовой плоскости . Две точки p и q соединены ребром, если все углы prq острее порога, определяемого числовым параметром β .
Определение на основе круга
Пусть β - положительное действительное число , и вычислим угол θ по формулам
Для любых двух точек p и q на плоскости пусть R pq будет набором точек, для которых угол prq больше θ . Тогда R pq принимает форму объединения двух открытых дисков диаметра βd ( p , q ) при β ≥ 1 и θ ≤ π / 2 и принимает форму пересечения двух открытых дисков диаметром d ( p , q ) / β для β ≤ 1 и θ ≥ π / 2. Когда β = 1, две формулы дают одно и то же значение θ = π / 2, а R pq принимает форму одного открытого диска с диаметром pq .
Β остов из дискретного множества S точек в плоскости является неориентированный граф , который соединяет две точки р и д с ребром рд всякий раз , когда R рд не содержит точек S . То есть β- скелет - это граф пустой области, определяемый областями R pq . [1] Когда S содержит точку r, для которой угол prq больше θ , тогда pq не является ребром β -скелета; β остов состоит из тех пар PQ , для которых нет такой точки г не существует.
Определение на основе Lune
Некоторые авторы используют альтернативное определение, в котором пустые области R pq для β > 1 являются не объединениями двух дисков, а скорее линзами (чаще называемыми в этом контексте « лунками »), пересечениями двух конгруэнтных дисков с диаметром βd ( pq ), такой, что отрезок pq лежит на радиусе обоих дисков, и точки p и q обе лежат на границе пересечения. Как и в случае окружности на основе β остов, луночка на основе β остов имеют край рд всякий раз , когда область R рда пусто от других входных точек. Для этого альтернативного определения граф относительных окрестностей является частным случаем β- скелета с β = 2. Два определения совпадают для β ≤ 1, а для больших значений β скелет на основе круга является подграфом лунного каркаса. на основе каркаса.
Одно важное различие между β- скелетами, основанными на круге и лунками, заключается в том, что для любого набора точек, который не лежит на одной линии, всегда существует достаточно большое значение β, такое, что β- скелет на основе круга является пустой граф . Напротив, если пара точек p и q обладает тем свойством, что для всех остальных точек r один из двух углов pqr и qpr является тупым, то β- скелет на основе луны будет содержать ребро pq независимо от того, насколько велик β является.
История
β -skeletons был впервые определен Киркпатрик & Radke (1985) в качестве масштабно-инвариантной вариации альфа - формы из Edelsbrunner, Киркпатрик & Сайдела (1983) . Название « β- скелет» отражает тот факт, что в некотором смысле β -скелет описывает форму набора точек так же, как топологический каркас описывает форму двумерной области. Также были рассмотрены некоторые обобщения β- скелета на графы, определяемые другими пустыми областями. [1] [2]
Характеристики
Если β непрерывно изменяется от 0 до ∞, β -скелеты на основе окружностей образуют последовательность графов, простирающуюся от полного графа до пустого графа . Частный случай β = 1 приводит к графу Габриэля , который, как известно, содержит евклидово минимальное остовное дерево ; следовательно, β -скелет также содержит граф Габриэля и минимальное остовное дерево, если β ≤ 1.
Для любого постоянная р , А фрактальная конструкция , напоминающая сплющенную версию снежинки Коха может использоваться , чтобы определить последовательность точечных множеств, β -skeletons являются путями сколь угодно большой длиной в пределах единичного квадрата. Следовательно, в отличие от тесно связанной триангуляции Делоне , β- скелеты имеют неограниченный фактор растяжения и не являются геометрическими ключами . [3]
Алгоритмы
Наивным алгоритм , который проверяет каждый тройной р , д и г на членство г в области R рд можно построить β остов любого множества п точек времени O ( п 3 ).
Когда β ≥ 1, β -скелет (с любым определением) является подграфом графа Габриэля, который является подграфом триангуляции Делоне . Если pq является ребром триангуляции Делоне, которое не является ребром β- скелета, то точка r, которая образует большой угол prq, может быть найдена как одна из не более двух точек, образующих треугольник с p и q в Триангуляция Делоне. Следовательно, для этих значений β круговой β- скелет для набора из n точек может быть построен за время O ( n log n ) путем вычисления триангуляции Делоне и использования этого теста для фильтрации его ребер. [2]
Для β <1 другой алгоритм Hurtado, Liotta & Meijer (2003) позволяет построить β- скелет за время O ( n 2 ). Лучшая временная граница для наихудшего случая невозможна, потому что для любого фиксированного значения β, меньшего единицы, существуют наборы точек в общем положении (небольшие возмущения правильного многоугольника ), для которых β- скелет является плотным графом с квадратичным числом краев. В том же квадратичном временном ограничении можно также рассчитать весь β- спектр (последовательность основанных на круге β- скелетов, образованных изменением β ).
Приложения
Β- скелет на основе круга может использоваться при анализе изображений для восстановления формы двумерного объекта по заданному набору точек выборки на границе объекта (вычислительная форма головоломки соединения точек, где последовательность в какие точки должны быть соединены, должно быть вычислено алгоритмом, а не дано как часть головоломки). Хотя, как правило, для этого требуется выбор значения параметра β , можно доказать, что выбор β = 1,7 правильно восстановит всю границу любой гладкой поверхности и не приведет к созданию ребер, не принадлежащих к граница, если образцы генерируются достаточно плотно относительно локальной кривизны поверхности. [4] Однако при экспериментальном тестировании более низкое значение, β = 1,2, было более эффективным для восстановления карт улиц из наборов точек, обозначающих центральные линии улиц в географической информационной системе . [5] Об обобщении техники β- скелета для реконструкции поверхностей в трех измерениях см. Hiyoshi (2007) .
Основанные на круге β -скелеты использовались для поиска подграфов триангуляции минимального веса набора точек: при достаточно больших значениях β каждое ребро β- скелета может гарантированно принадлежать к триангуляции минимального веса. Если найденные таким образом ребра образуют связный граф на всех входных точках, то оставшиеся ребра триангуляции минимального веса могут быть найдены за полиномиальное время с помощью динамического программирования . Однако в целом задача триангуляции минимального веса является NP-сложной, и подмножество ее ребер, найденное таким образом, может быть несвязным. [6]
бета -skeletons также применяется в области машинного обучения для решения геометрических классификационных задач [7] и в беспроводных одноранговых сетях в качестве механизма для управления сложностью связи путем выбора подмножества пар беспроводных станций , которые могут взаимодействовать друг с другом. [8]
Заметки
- ^ a b Кардинал, Коллетт и Лангерман (2009) .
- ^ а б Вельткамп (1992) .
- ^ Эпштайна (2002) ; Bose et al. (2002) ; Wang et al. (2003) .
- ^ Amenta, Bern & Эпштайна (1998) ; О'Рурк (2000) .
- ^ Радке & Flodmark (1999) .
- ^ Кейл (1994) ; Ченг и Сюй (2001) .
- ↑ Чжан и Кинг (2002) ; Туссен (2005) .
- ^ Bhardwaj, Мишра и Сюэ (2005) .
Рекомендации
- Амента, Нина ; Берн, Маршалл; Эпштейн, Дэвид (1998), «Кора и бета-скелет: реконструкция комбинаторной кривой» , Graphical Models & Image Processing , 60/2 (2): 125–135, заархивировано из оригинала 22 марта 2006 г. CS1 maint: обескураженный параметр ( ссылка ).
- Бхардвадж, Манвенду; Мишра, Сатьяджаянт; Сюэ, Гуолян (2005), «Распределенное управление топологией в беспроводных одноранговых сетях с использованием ß-скелета», Семинар по высокопроизводительной коммутации и маршрутизации (HPSR 2005), Гонконг, Китай (PDF) , заархивировано из оригинала (PDF) на 2011-06-07.
- Бозе, Просенджит ; Деврой, Люк; Эванс, Уильям; Киркпатрик, Дэвид Г. (2002), «О покрывающем отношении графов Габриэля и β- скелетов», LATIN 2002: теоретическая информатика , конспект лекций по информатике, 2286 , Springer-Verlag, стр. 77–97, doi : 10.1007 / 3-540-45995-2_42.
- Кардинал, Жан; Коллетт, Себастьян; Лангерман, Стефан (2009), "Пустые графы области", Вычислительная теория Геометрии и приложение , 42 (3): 183-195, DOI : 10.1016 / j.comgeo.2008.09.003.
- Ченг, Сиу-Винг; Сюй Инь-Feng (2001), "О β остов в качестве подграфа минимального веса триангуляции", Теоретическая информатика , 262 (1-2): 459-471, DOI : 10.1016 / S0304-3975 (00) 00318 -2.
- Эдельсбруннер, Герберт ; Киркпатрик, Дэвид Г .; Сейдел, Раймунд (1983), "О форме множества точек на плоскости", IEEE Transactions по теории информации , 29 (4): 551-559, DOI : 10,1109 / TIT.1983.1056714.
- Эпштейн, Дэвид (2002), «Бета-скелеты имеют неограниченное расширение», Computational Geometry Theory & Applications , 23 (1): 43–52, arXiv : cs.CG/9907031 , doi : 10.1016 / S0925-7721 (01) 00055 -4.
- Хиёси, Х. (2007), «Жадный бета-скелет в трех измерениях», Proc. 4 - й Международный симпозиум по Вороного в области науки и техники (ISVD 2007) , стр 101-109,. Дои : 10,1109 / ISVD.2007.27.
- Уртадо, Ферран ; Лиотта, Джузеппе; Мейер, Хенк (2003), «Оптимальные и субоптимальные робастные алгоритмы для графов близости», Теория вычислительной геометрии и приложения , 25 (1-2): 35–49, DOI : 10.1016 / S0925-7721 (02) 00129-3.
- Кейл, Дж. Марк (1994), "Вычисление подграфа триангуляции минимального веса", Computational Geometry Theory & Applications , 4 (1): 18–26, DOI : 10.1016 / 0925-7721 (94) 90014-0.
- Киркпатрик, Дэвид Г .; Радке, Джон Д. (1985), "Структура для вычислительной морфологии", Вычислительная геометрия , машинный интеллект и распознавание образов, 2 , Амстердам: Северная Голландия, стр. 217–248.
- О'Рурк, Джозеф (2000), "Computational Geometry Column 38", SIGACT News , 31 (1): 28–30, arXiv : cs.CG/0001025 , doi : 10.1145 / 346048.346050.
- Радке, Джон Д .; Флодмарк, Андерс (1999), «Использование пространственной декомпозиции для построения осевых линий улиц» (PDF) , Географические информационные науки , 5 (1): 15–23.
- Туссент, Годфрид (2005), «Геометрические графы близости для улучшения методов ближайшего соседа в обучении на основе экземпляров и интеллектуальном анализе данных», Международный журнал вычислительной геометрии и приложений , 15 (2): 101–150, DOI : 10,1142 / S0218195905001622.
- Veltkamp, Ремко С. (1992), "О γ-окрестности графика" (PDF) , Вычислительная теория и приложения Геометрия , 1 (4): 227-246, DOI : 10.1016 / 0925-7721 (92) 90003-B.
- Ван, Вэйчжао; Ли, Сян-Ян; Моавенинеджад, Коуша; Ван, Ю; Song, Wen-Zhan (2003), "Коэффициент охвата β- скелетов", Proc. 15-я Канадская конференция по вычислительной геометрии (CCCG 2003) (PDF) , стр. 35–38.
- Чжан, Ван; Кинг, Ирвин (2002), "Определение опорных векторов с помощью техники β- скелета", Proc. Материалы 9-й Международной конференции по обработке нейронной информации (ICONIP'02), Orchid Country Club, Сингапур, 18-22 ноября 2002 г. (PDF) , стр. 1423–1427.