Бета-скелет - 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]

Примечания

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