Бета-скелет - Beta skeleton

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

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

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

Пустые регионы р_pq определение круговой β-скелет. Оставили: β <1. Центр: β = 1. Вправо: β > 1.

Позволять β быть позитивным настоящий номер, и вычислить угол θ используя формулы

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

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

В β-скелет дискретный набор S точек на плоскости - это неориентированный граф который соединяет две точки п и q с краю pq в любое время р_pq не содержит точек S. Это β-skeleton - это пустой граф области, определяемый областями р_pq.^[1] Когда S содержит точку р под каким углом цена больше, чем θ, тогда pq не край β-скелет; то β-скелет состоит из этих пар pq для чего нет такой точки р существуют.

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

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

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

История

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

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

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

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

Алгоритмы

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

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

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

Приложения

Круговой β-скелет может использоваться в анализ изображений для восстановления формы двухмерного объекта по заданному набору точек выборки на границе объекта (вычислительная форма соедините точки головоломка, в которой последовательность, в которой должны быть соединены точки, должна быть выведена с помощью алгоритма, а не задана как часть головоломки). Хотя, в целом, для этого требуется выбор значения параметра β, можно доказать, что выбор β = 1,7 будет правильно реконструировать всю границу любой гладкой поверхности и не будет генерировать какие-либо ребра, которые не принадлежат границе, пока образцы генерируются достаточно плотно относительно локальной кривизна поверхности.^[4] Однако при экспериментальном тестировании более низкое значение, β = 1,2, был более эффективным для восстановления карт улиц из наборов точек, обозначающих центральные линии улиц в географическая информационная система.^[5] Для обобщения β-скелетная техника для реконструкции поверхностей в трех измерениях, см. Хиёси (2007).

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

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

Примечания

1. Кардинал, Коллетт и Лангерман (2009).
2. Вельткамп (1992).
3. Эппштейн (2002); Bose et al. (2002); Wang et al. (2003).
4. Амента, Берн и Эпштейн (1998); О'Рурк (2000).
5. Радке и Флодмарк (1999).
6. Кейл (1994); Ченг и Сюй (2001).
7. Чжан и Кинг (2002); Туссен (2005).
8. Бхардвадж, Мисра и Сюэ (2005).

Рекомендации

• Амента, Нина; Берн, Маршалл; Эппштейн, Дэвид (1998), «Кора и бета-скелет: реконструкция комбинаторной кривой», Графические модели и обработка изображений, 60/2 (2): 125–135, архивировано с оригинал на 2006-03-22.
• Бхардвадж, Манвенду; Мишра, Сатьяджаянт; Сюэ, Гуолян (2005), «Распределенное управление топологией в беспроводных одноранговых сетях с использованием ß-скелета», Семинар по высокопроизводительной коммутации и маршрутизации (HPSR 2005), Гонконг, Китай (PDF), заархивировано из оригинал (PDF) на 2011-06-07.
• Бозе, Просенджит; Деврой, Люк; Эванс, Уильям; Киркпатрик, Дэвид Г. (2002), "О покрываемости графов Габриэля и β-скелеты », ЛАТИН 2002: Теоретическая информатика., Конспект лекций по информатике, 2286, Springer-Verlag, стр. 77–97, Дои:10.1007/3-540-45995-2_42.
• Кардинал, Жан; Коллетт, Себастьян; Лангерман, Стефан (2009), «Графики пустых регионов», Теория вычислительной геометрии и приложения, 42 (3): 183–195, Дои:10.1016 / j.comgeo.2008.09.003.
• Ченг, Сиу-Винг; Сюй, Инь-Фэн (2001), «Он» β-скелет как подграф триангуляции минимального веса », Теоретическая информатика, 262 (1–2): 459–471, Дои:10.1016 / S0304-3975 (00) 00318-2.
• Эдельсбруннер, Герберт; Киркпатрик, Дэвид Г.; Зайдель, Раймунд (1983), «О форме множества точек на плоскости», IEEE Transactions по теории информации, 29 (4): 551–559, Дои:10.1109 / TIT.1983.1056714.
• Эппштейн, Дэвид (2002), «Бета-скелеты имеют неограниченное расширение», Теория вычислительной геометрии и приложения, 23 (1): 43–52, arXiv:cs.CG/9907031, Дои: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, Дои:10.1016 / S0925-7721 (02) 00129-3.
• Кейл, Дж. Марк (1994), "Вычисление подграфа триангуляции минимального веса", Теория вычислительной геометрии и приложения, 4 (1): 18–26, Дои:10.1016/0925-7721(94)90014-0.
• Киркпатрик, Дэвид Г.; Радке, Джон Д. (1985), "Фреймворк для вычислительной морфологии", Вычислительная геометрия, Машинный интеллект и распознавание образов, 2, Амстердам: Северная Голландия, стр. 217–248..
• О'Рурк, Джозеф (2000), «Вычислительная геометрия, столбец 38», Новости SIGACT, 31 (1): 28–30, arXiv:cs.CG/0001025, Дои:10.1145/346048.346050.
• Радке, Джон Д .; Флодмарк, Андерс (1999), «Использование пространственной декомпозиции для построения осевых линий улиц» (PDF), Географические информационные науки, 5 (1): 15–23.
• Туссен, Годфрид (2005), «Геометрические графы близости для улучшения методов ближайшего соседа в обучении на основе экземпляров и интеллектуальном анализе данных», Международный журнал вычислительной геометрии и приложений, 15 (2): 101–150, Дои:10.1142 / S0218195905001622.
• Вельткамп, Ремко С. (1992), «Граф γ-окрестности» (PDF), Теория вычислительной геометрии и приложения, 1 (4): 227–246, Дои:10.1016 / 0925-7721 (92) 90003-Б.
• Ван, Вэйчжао; Ли, Сян-Ян; Моавенинеджад, Коуша; Ван, Ю; Сун, Вэнь-Чжань (2003), «Коэффициент охвата β-скелеты », Proc. 15-я Канадская конференция по вычислительной геометрии (CCCG 2003) (PDF), стр. 35–38.
• Чжан, Ван; Кинг, Ирвин (2002), "Определение опорных векторов с помощью β-скелетная техника », Proc. Труды 9-й Международной конференции по обработке нейронной информации (ICONIP'02), Orchid Country Club, Сингапур, 18-22 ноября 2002 г. (PDF), стр. 1423–1427.