Бета-скелет

Основанный на круге скелет 1.1 (толстые темные края) и скелет 0.9 (светлые пунктирные синие края) набора из 100 случайных точек в квадрате.

В вычислительной геометрии и геометрической теории графов или β -скелет бета -скелет представляет собой неориентированный граф, определенный из набора точек на евклидовой плоскости . Две точки p и q соединяются ребром всякий раз, когда все углы prq острее порога, определенного из числового параметра β .

Определение на основе круга

Пустые области R _pq, скелет на основе круга определяющие β- . Слева: β < 1. В центре: β = 1. Справа: β > 1.

Пусть β — положительное действительное число , и вычислите угол θ по формулам

$\theta ={\begin{cases}\sin ^{-1}{\frac {1}{\beta }},&{\text{if }}\beta \geq 1\\\pi -\sin ^{-1}{\beta },&{\text{if }}\beta \leq 1\end{cases}}$

Для любых двух точек p и q на плоскости пусть R _pq будет множеством точек, для которых угол prq больше θ . Тогда R _pq принимает вид объединения двух открытых дисков диаметром βd ( p , q ) при β ≥ 1 и θ ≤ π/2 и принимает вид пересечения двух открытых дисков диаметром d ( p , q )/ β для β ≤ 1 и θ ≥ π/2. Когда β = 1, две формулы дают одно и то же значение θ = π/2, а R _pq принимает форму одного открытого диска с pq диаметром .

- скелет β дискретного множества S точек на плоскости — это неориентированный граф , соединяющий две точки p и q с ребром pq, R pq _не содержит точек из S. если То есть β -скелет представляет собой граф пустых областей, определяемый областями R _pq . Если S содержит точку r, для которой угол prq больше θ , то pq не является ребром β -скелета; β , -остов состоит из тех пар pq для которых такой точки r не существует.

Определение на основе лун

Некоторые авторы используют альтернативное определение, в котором пустые области R _pq при β > 1 представляют собой не объединения двух дисков, а скорее линзы (чаще называемые в этом контексте « лунами »), пересечения двух конгруэнтных дисков диаметром βd ( pq ), такой, что отрезок pq лежит на радиусе обоих дисков и такой, что обе точки p и q лежат на границе пересечения. -скелета на основе круга Как и в случае β -скелет на основе луны , β имеет ребро pq всякий раз, когда область R _pq пуста из других входных точек. Для этого альтернативного определения граф относительной окрестности является частным случаем β -скелета с β = 2. Оба определения совпадают при β ≤ 1, а для больших значений β скелет на основе круга является подграфом лунного скелета. основанный скелет.

-скелетами на основе круга и луны Одно важное различие между β состоит в том, что для любого набора точек, который не лежит на одной прямой, всегда существует достаточно большое значение β на основе круга такое, что β -скелет пустой граф . Напротив, если пара точек p и q обладает свойством, что для всех остальных точек r один из двух углов pqr и qpr тупой, то β -скелет на основе луны будет содержать ребро pq независимо от того, насколько велико β. является.

История

β -скелеты были впервые определены Киркпатриком и Радке (1985) как масштабно-инвариантная вариация альфа -форм Эдельсбруннера , Киркпатрика и Зейделя (1983) . Название « β -скелет» отражает тот факт, что в некотором смысле β -скелет описывает форму набора точек таким же образом, как топологический скелет описывает форму двумерной области. Также были рассмотрены несколько обобщений β -скелета на графы, определяемые другими пустыми областями.

Характеристики

Если β -скелеты на основе окружностей непрерывно меняется от 0 до ∞, β образуют последовательность графов, простирающуюся от полного графа к пустому графу . Особый случай β = 1 приводит к графу Габриэля , который, как известно, содержит евклидово минимальное остовное дерево ; следовательно, β -скелет также содержит граф Габриэля и минимальное остовное дерево, если β ≤ 1.

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

Алгоритмы

Наивный алгоритм , проверяющий каждую тройку p , q и r на принадлежность r к области R _pq, может построить β -скелет любого набора из n точек за время O( n ³ ).

Когда β ≥ 1, β -скелет (с любым определением) является подграфом графа Габриэля, который является подграфом триангуляции Делоне . Если pq — ребро триангуляции Делоне, не являющееся ребром β -остова, то точку r , образующую большой угол prq, можно найти как одну из не более чем двух точек, образующих треугольник с p и q в Триангуляция Делоне. Следовательно, для этих значений β -скелет на основе круга β для набора из n точек может быть построен за время O( n log n ) путем вычисления триангуляции Делоне и использования этого теста для фильтрации ее ребер.

Для β < 1 другой алгоритм Уртадо, Лиотты и Мейера (2003) позволяет построить β -скелет за время O( n ² ). Лучшей оценки времени для наихудшего случая быть не может, поскольку для любого фиксированного значения β, меньшего единицы, существуют множества точек общего положения (малые возмущения правильного многоугольника ), для которых β -скелет представляет собой плотный граф с квадратичным числом. краев. весь β -спектр (последовательность β- скелетов на основе кругов, образованных путем изменения β За тот же квадратичный временной интервал можно также вычислить ).

Приложения

скелет на основе круга β- может использоваться при анализе изображений для восстановления формы двумерного объекта по набору точек выборки на границе объекта (вычислительная форма головоломки « Соедини точки» , где последовательность в точки, которые должны быть соединены, должны определяться алгоритмом, а не задаваться как часть головоломки). Хотя, вообще говоря, для этого требуется выбор значения параметра β , можно доказать, что выбор β = 1,7 позволит правильно восстановить всю границу любой гладкой поверхности и не генерировать никаких ребер, не принадлежащих границы, при условии, что образцы генерируются достаточно плотно относительно локальной кривизны поверхности. Однако в ходе экспериментального тестирования более низкое значение, β = 1,2, было более эффективным для восстановления карт улиц по наборам точек, обозначающих центральные линии улиц в географической информационной системе . Обобщение метода β -скелета для реконструкции поверхностей в трех измерениях см. в Hiyoshi (2007) .

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

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

Ссылки

• Амента, Нина ; Берн, Маршалл; Эппштейн, Дэвид (1998), «Кора и бета-скелет: реконструкция комбинаторной кривой» , Графические модели и обработка изображений , 60/2 (2): 125–135, doi : 10.1006/gmip.1998.0465 , S2CID   6301659 , в архиве из оригинала от 22 марта 2006 г.
• Бхардвадж, Манвенду; Мишра, Сатьяджаянт; Сюэ, Гуолян (2005 г.), «Управление распределенной топологией в беспроводных одноранговых сетях с использованием ß-скелета», Семинар по высокопроизводительной коммутации и маршрутизации (HPSR 2005), Гонконг, Китай (PDF) , заархивировано из оригинала (PDF) на 07.06.2011 .
• Бозе, Просенджит ; Деврой, Люк; Эванс, Уильям; Киркпатрик, Дэвид Г. (2002), «О соотношении охвата графов Габриэля и β -скелетов», LATIN 2002: Теоретическая информатика , Конспекты лекций по информатике, том. 2286, Springer-Verlag, стр. 77–97, номер документа : 10.1007/3-540-45995-2_42 , ISBN.  978-3-540-43400-9 .
• Кардинал, Жан; Коллетт, Себастьян; Лангерман, Стефан (2009), «Графы пустых областей», Теория и приложения вычислительной геометрии , 42 (3): 183–195, doi : 10.1016/j.comgeo.2008.09.003 .
• Ченг, Сиу-Винг; Сюй, Инь-Фэн (2001), «О β -скелете как подграфе триангуляции минимального веса», Theoretical Computer Science , 262 (1–2): 459–471, doi : 10.1016/S0304-3975(00)00318 -2 .
• Эдельсбруннер, Герберт ; Киркпатрик, Дэвид Г .; Зайдель, Раймунд (1983), «О форме множества точек на плоскости», IEEE Transactions on Information Theory , 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 , S2CID   1617451 .
• Хиёси, Х. (2007), «Жадный бета-скелет в трех измерениях», Proc. 4-й Международный симпозиум по диаграммам Вороного в науке и технике (ISVD 2007) , стр. 101–109, doi : 10.1109/ISVD.2007.27 , ISBN  978-0-7695-2869-4 , S2CID   23189942 .
• Уртадо, Ферран ; Лиотта, Джузеппе; Мейер, Хенк (2003), «Оптимальные и субоптимальные надежные алгоритмы для графов близости», Computational Geometry Theory & Applications , 25 (1–2): 35–49, doi : 10.1016/S0925-7721(02)00129-3 , S2CID   14573479 .
• Кейл, Дж. Марк (1994), «Вычисление подграфа триангуляции минимального веса», Computational Geometry Theory & Applications , 4 (1): 18–26, doi : 10.1016/0925-7721(94)90014-0 .
• Киркпатрик, Дэвид Г .; Радке, Джон Д. (1985), «Основы вычислительной морфологии», Вычислительная геометрия , машинный интеллект и распознавание образов, том. 2, Амстердам: Северная Голландия, стр. 217–248 .
• О'Рурк, Джозеф (2000), «Столбец 38 по вычислительной геометрии», SIGACT News , 31 (1): 28–30, arXiv : cs.CG/0001025 , doi : 10.1145/346048.346050 .
• Радке, Джон Д.; Флодмарк, Андерс (1999), «Использование пространственного разложения для построения осевых линий улиц» (PDF) , Geographic Information Sciences , 5 (1): 15–23, Бибкод : 1999AnGIS...5...15R , doi : 10.1080 /10824009909480509 .
• Туссен, Годфрид (2005), «Геометрические графы близости для улучшения методов ближайшего соседа в обучении на основе экземпляров и интеллектуальном анализе данных», International Journal of Computational Geometry and Applications , 15 (2): 101–150, doi : 10.1142/S0218195905001622 .
• Велткамп, Ремко К. (1992), «Граф γ-соседства» (PDF) , Теория вычислительной геометрии и приложения , 1 (4): 227–246, doi : 10.1016/0925-7721(92)90003-B .
• Ван, Вэйчжао; Ли, Сян-Ян; Моавенинежад, Куша; Ван, Ю; Сун, Вэнь-Чжан (2003), «Коэффициент охвата β- скелетов», Proc. 15-я Канадская конференция по вычислительной геометрии (CCCG 2003) (PDF) , стр. 35–38 .
• Чжан, Ван; Кинг, Ирвин (2002), «Определение опорных векторов с помощью β метода -скелета», Proc. Материалы 9-й Международной конференции по нейронной обработке информации (ICONIP'02), Orchid Country Club, Сингапур, 18–22 ноября 2002 г. (PDF) , стр. 1423–1427 .