Бета-остов

-остов, бета-остов или бета-скелет — это ориентированный граф, определённый на множестве точек на евклидовой плоскости. Две точки p and q связаны ребром, когда все углы prq меньше некоторого порога, определённого параметром .

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

Пусть  будет положительным вещественным числом, вычислим угол  по формулам

 

Для любых двух точек p и q на плоскости пусть Rpq будет множеством точек, для которых угол prq больше . Тогда Rpq принимает вид объединения двух открытых дисков с диаметром  для  и  и принимает форму пересечения двух открытых дисков диаметра  для  и . Когда  две формулы дают то же самое значение,  и Rpq принимает форму одного открытого диска с pq в качестве диаметра.

-остов дискретного множества S точек плоскости — это неориентированный граф, который соединяет две точки p и q ребром pq, когда Rpq не содержит точек S. То есть -остов является графом пустых пространств, определённых областями Rpq. Если S содержит точку r, для которой угол prq больше , то pq не является ребром -остова. -остов состоит из тех пар pq, для которых такая точка r существует.

Определение на основе линз 
Некоторые авторы используют альтернативное определение, в котором пустые области Rpq для  являются не объединением двух дисков, а , пересечением двух дисков с диаметрами , таких, что отрезок pq лежит на радиусах обоих дисков, так что обе точки p и q лежат на границе пересечения. Как и в случае основанного на окружностях -остова, основанный на линзах -остов имеет ребро pq, когда область Rpq пуста от других точек. Для этого альтернативного определения, граф относительных окрестностей является специальным случаем -остова с . Два определения совпадает для , а для бо́льших значений  основанный на окружностях остов является подграфом основанного на линзах остова.

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

История 
-остова первым определили Киркпатрик и Радке как масштабно инвариантный вариант альфа-формы Эдельсбруннера, Киркпатрика и Зайделя. Название -остов отражает факт, что в некотором смысле -остов описывает форму множества точек таким же образом, как топологический скелет описывает форму двумерной области. Рассматривались также обобщения -остова графов, определёнными другими пустыми областями .

Свойства 
Если  меняется непрерывно от 0 до , основанные на окружности -остова образуют последовательность графов от полного графа до пустого графа. Специальный случай  ведёт к графу Габриэля, который, как известно, содержат евклидово минимальное остовное дерево. Поэтому -остов также содержит граф Габриэля и минимальное остовное дерево, если .

Для любой постоянной  построение фрактала, который напоминает сглаженную версию снежинки Коха, может быть использовано для определения последовательности точечных множеств, -остова которых являются путями произвольно большой длины в единичном квадрате. Поэтому, в отличие от тесно связанной триангуляции Делоне, -остова имеют неограниченный  и не являются геометрическими остовами.

Алгоритмы 
Простой естественный алгоритм, который проверяет каждую тройку p, q и r на принадлежность точки r области Rpq, может построить -остов любого множества с n точками за время O(n3).

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

Для  другой алгоритм Уртадо, Лиотты и Meijer позволяет построить -остов за время O(n2). Никакой лучшей границы для времени в худшем случае не существует, поскольку для любого фиксированного значения , меньшего единицы, существуют множества точек в общем положении (небольшие возмущения правильного многоугольника), для которых -остов является плотным графом с квадратным числом рёбер. В тех же квадратичных временных границах можно вычислить весь -спектр (последовательность основанных на окружностях -остовов, получающихся изменением ).

Приложения 
Основанный на окружностях -остов может быть использован в  при восстановлении формы двухмерного объекта, если дано множество точек на границе объекта (вычислительный аналог головоломки , где последовательность, в которой точки нужно связать, не заданы заранее как часть головоломки, а их алгоритм должен вычислить). Хотя, в общем случае, это требует выбора значения параметра , можно доказать, что выбор  будет правильно восстанавливать всю границу любой гладкой поверхности и не будет создавать любое ребро, которое не принадлежит границе, так как точки генерируются достаточно плотно относительно локальной кривизны поверхности. Однако в экспериментальных тестах меньшее значение  было более эффективно для восстановления карты улиц по множеству точек, отображающих центральные линии улиц в геоинформационной системе. Как обобщение техники -остова для восстановления поверхностей в трёхмерном пространстве, см. .

Основанные на окружностях -остова использовались для поиска графов  множества точек — для достаточно больших значений  любое ребро -остова гарантированно принадлежит минимальной взвешенной триангуляции. Если рёбра, найденные таким образом, образуют связный граф на всех точках, то оставшиеся рёбра минимальной взвешенной триангуляции могут быть найдены за полиномиальное время с помощью динамического программирования. Однако, в общем случае, задача минимальной взвешенной триангуляции является NP-трудной задачей и подмножество рёбер, найденных таким образом, может не быть связным.

-остова были также применены в машинном обучении для задач геометрической классификации и в беспроводных ad-hoc-сетях в качестве механизма контроля сложности сети путём выбора подмножества пар беспроводных станций, которые могут общаться друг с другом.

Примечания

Литература 

 .
 .
 
 
 .
 
 .
 .
 
 .
 .
 
 
 
 
 
 

Планиметрия
Геометрические графы
Вычислительная геометрия