Бета-остов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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