Перейти к содержанию

Бета-остов

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

[math]\displaystyle{ \boldsymbol{\beta} }[/math]-остов, бета-остов или бета-скелет — это ориентированный граф, определённый на множестве точек на евклидовой плоскости. Две точки p and q связаны ребром, когда все углы prq меньше некоторого порога, определённого параметром [math]\displaystyle{ \beta }[/math].

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

Пустые пространства [math]\displaystyle{ R_{pq} }[/math], определяющие основанный на окружностях [math]\displaystyle{ \beta }[/math]-остов. Слева: [math]\displaystyle{ \beta \lt 1 }[/math]. Центр: [math]\displaystyle{ \beta=1 }[/math]. Справа: [math]\displaystyle{ \beta \gt 1 }[/math].

Пусть [math]\displaystyle{ \beta }[/math] будет положительным вещественным числом, вычислим угол [math]\displaystyle{ \theta }[/math] по формулам

[math]\displaystyle{ \theta=\begin{cases} \sin^{-1} \frac{1}{\beta}, & & \beta \geqslant 1 \\ \pi - \sin^{-1}{\beta}, & & \beta\leqslant 1\end{cases} }[/math]

Для любых двух точек p и q на плоскости пусть Rpq будет множеством точек, для которых угол prq больше [math]\displaystyle{ \theta }[/math]. Тогда Rpq принимает вид объединения двух открытых дисков с диаметром [math]\displaystyle{ \beta{d}(p,q) }[/math] для [math]\displaystyle{ \beta \geqslant 1 }[/math] и [math]\displaystyle{ \theta \leqslant \pi/2 }[/math] и принимает форму пересечения двух открытых дисков диаметра [math]\displaystyle{ d(p,q)/\beta }[/math] для [math]\displaystyle{ \beta \leqslant 1 }[/math] и [math]\displaystyle{ \theta \geqslant \pi/2 }[/math]. Когда [math]\displaystyle{ \beta=1 }[/math] две формулы дают то же самое значение, [math]\displaystyle{ \theta=\pi/2 }[/math] и Rpq принимает форму одного открытого диска с pq в качестве диаметра.

[math]\displaystyle{ \beta }[/math]-остов дискретного множества S точек плоскости — это неориентированный граф, который соединяет две точки p и q ребром pq, когда Rpq не содержит точек S. То есть [math]\displaystyle{ \beta }[/math]-остов является графом пустых пространств, определённых областями Rpq[1]. Если S содержит точку r, для которой угол prq больше [math]\displaystyle{ \theta }[/math], то pq не является ребром [math]\displaystyle{ \beta }[/math]-остова. [math]\displaystyle{ \beta }[/math]-остов состоит из тех пар pq, для которых такая точка r существует.

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

Некоторые авторы используют альтернативное определение, в котором пустые области Rpq для [math]\displaystyle{ \beta \gt 1 }[/math] являются не объединением двух дисков, а линзой[англ.], пересечением двух дисков с диаметрами [math]\displaystyle{ \beta{d}(pq) }[/math], таких, что отрезок pq лежит на радиусах обоих дисков, так что обе точки p и q лежат на границе пересечения. Как и в случае основанного на окружностях [math]\displaystyle{ \beta }[/math]-остова, основанный на линзах [math]\displaystyle{ \beta }[/math]-остов имеет ребро pq, когда область Rpq пуста от других точек. Для этого альтернативного определения, граф относительных окрестностей является специальным случаем [math]\displaystyle{ \beta }[/math]-остова с [math]\displaystyle{ \beta=2 }[/math]. Два определения совпадает для [math]\displaystyle{ \beta \leqslant 1 }[/math], а для бо́льших значений [math]\displaystyle{ \beta }[/math] основанный на окружностях остов является подграфом основанного на линзах остова.

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

История

[math]\displaystyle{ \beta }[/math]-остова первым определили Киркпатрик и Радке[2] как масштабно инвариантый вариант альфа-формы Эдельсбруннера, Киркпатрика и Зайделя[3]. Название [math]\displaystyle{ \beta }[/math]-остов отражает факт, что в некотором смысле [math]\displaystyle{ \beta }[/math]-остов описывает форму множества точек таким же образом, как топологический скелет описывает форму двумерной области. Рассматривались также обобщения [math]\displaystyle{ \beta }[/math]-остова графов, определёнными другими пустыми областями [1][4].

Свойства

Если [math]\displaystyle{ \beta }[/math] меняется непрерывно от 0 до [math]\displaystyle{ \infty }[/math], основанные на окружности [math]\displaystyle{ \beta }[/math]-остова образуют последовательность графов от полного графа до пустого графа. Специальный случай [math]\displaystyle{ \beta=1 }[/math] ведёт к графу Габриэля, который, как известно, содержат евклидово минимальное остовное дерево. Поэтому [math]\displaystyle{ \beta }[/math]-остов также содержит граф Габриэля и минимальное остовное дерево, если [math]\displaystyle{ \beta \leqslant 1 }[/math].

Для любой постоянной [math]\displaystyle{ \beta }[/math] построение фрактала, который напоминает сглаженную версию снежинки Коха, может быть использовано для определения последовательности точечных множеств, [math]\displaystyle{ \beta }[/math]-остова которых являются путями произвольно большой длины в единичном квадрате. Поэтому, в отличие от тесно связанной триангуляции Делоне, [math]\displaystyle{ \beta }[/math]-остова имеют неограниченный коэффициент растяжения[англ.] и не являются геометрическими остовами[5][6][7].

Алгоритмы

Простой естественный алгоритм, который проверяет каждую тройку p, q и r на принадлежность точки r области Rpq, может построить [math]\displaystyle{ \beta }[/math]-остов любого множества с n точками за время O(n3).

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

Для [math]\displaystyle{ \beta \lt 1 }[/math] другой алгоритм Уртадо, Лиотты и Meijer[8] позволяет построить [math]\displaystyle{ \beta }[/math]-остов за время O(n2). Никакой лучшей границы для времени в худшем случае не существует, поскольку для любого фиксированного значения [math]\displaystyle{ \beta }[/math], меньшего единицы, существуют множества точек в общем положении (небольшие возмущения правильного многоугольника), для которых [math]\displaystyle{ \beta }[/math]-остов является плотным графом с квадратным числом рёбер. В тех же квадратичных временных границах можно вычислить весь [math]\displaystyle{ \beta }[/math]-спектр (последовательность основанных на окружностях [math]\displaystyle{ \beta }[/math]-остовов, получающихся изменением [math]\displaystyle{ \beta }[/math]).

Приложения

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

Основанные на окружностях [math]\displaystyle{ \beta }[/math]-остова использовались для поиска графов минимальной взвешенной триангуляции[англ.] множества точек — для достаточно больших значений [math]\displaystyle{ \beta }[/math] любое ребро [math]\displaystyle{ \beta }[/math]-остова гарантированно принадлежит минимальной взвешенной триангуляции. Если рёбра, найденные таким образом, образуют связный граф на всех точках, то оставшиеся рёбра минимальной взвешенной триангуляции могут быть найдены за полиномиальное время с помощью динамического программирования. Однако, в общем случае, задача минимальной взвешенной триангуляции является NP-трудной задачей и подмножество рёбер, найденных таким образом, может не быть связным[12][13].

[math]\displaystyle{ \beta }[/math]-остова были также применены в обучении машин для задач геометрической классификации[14][15] и в беспроводных ad-hoc-сетях в качестве механизма контроля сложности сети путём выбора подмножества пар беспроводных станций, которые могут общаться друг с другом[16].

Примечания

Литература