Бета-остов

$\mathit{\beta <!--\; \beta \; -->}$${\boldsymbol {\beta }}$-остов, бета-остов или бета-скелет — это ориентированный граф, определённый на множестве точек на евклидовой плоскости. Две точки p and q связаны ребром, когда все углы prq меньше некоторого порога, определённого параметром $\mathrm{\beta <!--\; \beta \; -->}$$\beta$.

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

Определение на основе окружностейПравить

 

Пустые пространства $R_{pq}$$R_{pq}$ , определяющие основанный на окружностях $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов. Слева: $\beta <1$ . Центр: $\mathrm{\beta <!--\; \beta \; -->}=1$$\beta =1$ . Справа: $\mathrm{\beta <!--\; \beta \; -->}>1$$\beta >1$ .

Пусть $\mathrm{\beta <!--\; \beta \; -->}$$\beta$  будет положительным вещественным числом, вычислим угол $\mathrm{\theta <!--\; \theta \; -->}$$\theta$  по формулам

$\theta ={\begin{cases}\sin ^{-1}{\frac {1}{\beta }},&&\beta \geqslant 1\\\pi -\sin ^{-1}{\beta },&&\beta \leqslant 1\end{cases}}$ 

Для любых двух точек p и q на плоскости пусть R_pq будет множеством точек, для которых угол prq больше $\mathrm{\theta <!--\; \theta \; -->}$$\theta$ . Тогда R_pq принимает вид объединения двух открытых дисков с диаметром $\mathrm{\beta <!--\; \beta \; -->}d(p,q)$$\beta {d}(p,q)$  для $\mathrm{\beta <!--\; \beta \; -->}⩾<!--\; ⩾\; -->1$$\beta \geqslant 1$  и $\mathrm{\theta <!--\; \theta \; -->}⩽<!--\; ⩽\; -->\mathrm{\pi <!--\; \pi \; -->}/2$$\theta \leqslant \pi /2$  и принимает форму пересечения двух открытых дисков диаметра $d(p,q)/\mathrm{\beta <!--\; \beta \; -->}$$d(p,q)/\beta$  для $\mathrm{\beta <!--\; \beta \; -->}⩽<!--\; ⩽\; -->1$$\beta \leqslant 1$  и $\mathrm{\theta <!--\; \theta \; -->}⩾<!--\; ⩾\; -->\mathrm{\pi <!--\; \pi \; -->}/2$$\theta \geqslant \pi /2$ . Когда $\mathrm{\beta <!--\; \beta \; -->}=1$$\beta =1$  две формулы дают то же самое значение, $\mathrm{\theta <!--\; \theta \; -->}=\mathrm{\pi <!--\; \pi \; -->}/2$$\theta =\pi /2$  и R_pq принимает форму одного открытого диска с pq в качестве диаметра.

$\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов дискретного множества S точек плоскости — это неориентированный граф, который соединяет две точки p и q ребром pq, когда R_pq не содержит точек S. То есть $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов является графом пустых пространств, определённых областями R_pq. Если S содержит точку r, для которой угол prq больше $\mathrm{\theta <!--\; \theta \; -->}$$\theta$ , то pq не является ребром $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остова. $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов состоит из тех пар pq, для которых такая точка r существует.

Определение на основе линзПравить

Некоторые авторы используют альтернативное определение, в котором пустые области R_pq для $\mathrm{\beta <!--\; \beta \; -->}>1$$\beta >1$  являются не объединением двух дисков, а линзой^[en], пересечением двух дисков с диаметрами $\mathrm{\beta <!--\; \beta \; -->}d(pq)$$\beta {d}(pq)$ , таких, что отрезок pq лежит на радиусах обоих дисков, так что обе точки p и q лежат на границе пересечения. Как и в случае основанного на окружностях $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остова, основанный на линзах $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов имеет ребро pq, когда область R_pq пуста от других точек. Для этого альтернативного определения, граф относительных окрестностей является специальным случаем $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остова с $\mathrm{\beta <!--\; \beta \; -->}=2$$\beta =2$ . Два определения совпадает для $\mathrm{\beta <!--\; \beta \; -->}⩽<!--\; ⩽\; -->1$$\beta \leqslant 1$ , а для бо́льших значений $\mathrm{\beta <!--\; \beta \; -->}$$\beta$  основанный на окружностях остов является подграфом основанного на линзах остова.

Одна важная разница между основанных на окружностях и основанных на линзах $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остовов заключается в том, что для любого множества точек, которые не лежат на одной прямой, всегда существует достаточно большое значение $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ , такое, что основанный на окружностях $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов является пустым графом. Для контраста, если пара точек p и q имеет свойство, что для любой точки r один из двух углов pqr и qpr тупой, то основанный на линзах $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов будет содержать ребро pq независимо от того, насколько велико значение $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ .

ИсторияПравить

$\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остова первым определили Киркпатрик и Радке как масштабно инвариантый вариант альфа-формы Эдельсбруннера, Киркпатрика и Зайделя. Название $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов отражает факт, что в некотором смысле $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов описывает форму множества точек таким же образом, как топологический скелет описывает форму двумерной области. Рассматривались также обобщения $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остова графов, определёнными другими пустыми областями .

СвойстваПравить

Если $\mathrm{\beta <!--\; \beta \; -->}$$\beta$  меняется непрерывно от 0 до $\mathrm{\infty <!--\; \infty \; -->}$$\infty$ , основанные на окружности $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остова образуют последовательность графов от полного графа до пустого графа. Специальный случай $\mathrm{\beta <!--\; \beta \; -->}=1$$\beta =1$  ведёт к графу Габриэля, который, как известно, содержат евклидово минимальное остовное дерево. Поэтому $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов также содержит граф Габриэля и минимальное остовное дерево, если $\mathrm{\beta <!--\; \beta \; -->}⩽<!--\; ⩽\; -->1$$\beta \leqslant 1$ .

Для любой постоянной $\mathrm{\beta <!--\; \beta \; -->}$$\beta$  построение фрактала, который напоминает сглаженную версию снежинки Коха, может быть использовано для определения последовательности точечных множеств, $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остова которых являются путями произвольно большой длины в единичном квадрате. Поэтому, в отличие от тесно связанной триангуляции Делоне, $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остова имеют неограниченный коэффициент растяжения^[en] и не являются геометрическими остовами.

АлгоритмыПравить

Простой естественный алгоритм, который проверяет каждую тройку p, q и r на принадлежность точки r области R_pq, может построить $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов любого множества с n точками за время O(n³).

Когда $\mathrm{\beta <!--\; \beta \; -->}⩾<!--\; ⩾\; -->1$$\beta \geqslant 1$ , $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов (в любом определении) является подграфом графа Габриэля, который является подграфом триангуляции Делоне. Если pq является ребром триангуляции Делоне, но не является ребром $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остова, то точка r, которая образует больший угол prq, может быть найдена как одна из двух точек, образующих треугольник с точками p и q в триангуляции Делоне. Поэтому для этих значений $\mathrm{\beta <!--\; \beta \; -->}$$\beta$  основанный на окружностях $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов для множества n точек может быть построен за время O(n log n) путём вычисления триангуляции Делоне и используя этот тест как фильтр для рёбер.

Для $\beta <1$  другой алгоритм Уртадо, Лиотты и Meijer позволяет построить $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов за время O(n²). Никакой лучшей границы для времени в худшем случае не существует, поскольку для любого фиксированного значения $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ , меньшего единицы, существуют множества точек в общем положении (небольшие возмущения правильного многоугольника), для которых $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов является плотным графом с квадратным числом рёбер. В тех же квадратичных временных границах можно вычислить весь $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -спектр (последовательность основанных на окружностях $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остовов, получающихся изменением $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ ).

ПриложенияПравить

Основанный на окружностях $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остов может быть использован в анализе изображений^[en] при восстановлении формы двухмерного объекта, если дано множество точек на границе объекта (вычислительный аналог головоломки «Соединить точки»^[en], где последовательность, в которой точки нужно связать, не заданы заранее как часть головоломки, а их алгоритм должен вычислить). Хотя, в общем случае, это требует выбора значения параметра $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ , можно доказать, что выбор $\mathrm{\beta <!--\; \beta \; -->}=1,7$$\beta =1{,}7$  будет правильно восстанавливать всю границу любой гладкой поверхности и не будет создавать любое ребро, которое не принадлежит границе, так как точки генерируются достаточно плотно относительно локальной кривизны поверхности. Однако в экспериментальных тестах меньшее значение $\mathrm{\beta <!--\; \beta \; -->}=1,2$$\beta =1{,}2$  было более эффективно для восстановления карты улиц по множеству точек, отображающих центральные линии улиц в геоинформационной системе. Как обобщение техники $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остова для восстановления поверхностей в трёхмерном пространстве, см. Hiyoshi (2007).

Основанные на окружностях $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остова использовались для поиска графов минимальной взвешенной триангуляции^[en] множества точек — для достаточно больших значений $\mathrm{\beta <!--\; \beta \; -->}$$\beta$  любое ребро $\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остова гарантированно принадлежит минимальной взвешенной триангуляции. Если рёбра, найденные таким образом, образуют связный граф на всех точках, то оставшиеся рёбра минимальной взвешенной триангуляции могут быть найдены за полиномиальное время с помощью динамического программирования. Однако, в общем случае, задача минимальной взвешенной триангуляции является NP-трудной задачей и подмножество рёбер, найденных таким образом, может не быть связным.

$\mathrm{\beta <!--\; \beta \; -->}$$\beta$ -остова были также применены в машинном обучении для задач геометрической классификации и в беспроводных ad-hoc-сетях в качестве механизма контроля сложности сети путём выбора подмножества пар беспроводных станций, которые могут общаться друг с другом.