Русская Википедия:Бета-остов

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

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

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

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

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

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

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

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

История

<math>\beta</math>-остова первым определили Киркпатрик и РадкеШаблон:Sfn как масштабно инвариантый вариант альфа-формы Эдельсбруннера, Киркпатрика и ЗайделяШаблон:Sfn. Название <math>\beta</math>-остов отражает факт, что в некотором смысле <math>\beta</math>-остов описывает форму множества точек таким же образом, как топологический скелет описывает форму двумерной области. Рассматривались также обобщения <math>\beta</math>-остова графов, определёнными другими пустыми областями Шаблон:SfnШаблон:Sfn.

Свойства

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

Для любой постоянной <math>\beta</math> построение фрактала, который напоминает сглаженную версию снежинки Коха, может быть использовано для определения последовательности точечных множеств, <math>\beta</math>-остова которых являются путями произвольно большой длины в единичном квадрате. Поэтому, в отличие от тесно связанной триангуляции Делоне, <math>\beta</math>-остова имеют неограниченный Шаблон:Не переведено 5 и не являются геометрическими остовамиШаблон:SfnШаблон:SfnШаблон:Sfn.

Алгоритмы

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

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

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

Приложения

Основанный на окружностях <math>\beta</math>-остов может быть использован в Шаблон:Не переведено 5 при восстановлении формы двухмерного объекта, если дано множество точек на границе объекта (вычислительный аналог головоломки Шаблон:Не переведено 5, где последовательность, в которой точки нужно связать, не заданы заранее как часть головоломки, а их алгоритм должен вычислить). Хотя, в общем случае, это требует выбора значения параметра <math>\beta</math>, можно доказать, что выбор <math>\beta=1{,}7</math> будет правильно восстанавливать всю границу любой гладкой поверхности и не будет создавать любое ребро, которое не принадлежит границе, так как точки генерируются достаточно плотно относительно локальной кривизны поверхностиШаблон:SfnШаблон:Sfn. Однако в экспериментальных тестах меньшее значение <math>\beta=1{,}2</math> было более эффективно для восстановления карты улиц по множеству точек, отображающих центральные линии улиц в геоинформационной системеШаблон:Sfn. Как обобщение техники <math>\beta</math>-остова для восстановления поверхностей в трёхмерном пространстве, см. Шаблон:Harvtxt.

Основанные на окружностях <math>\beta</math>-остова использовались для поиска графов Шаблон:Не переведено 5 множества точек — для достаточно больших значений <math>\beta</math> любое ребро <math>\beta</math>-остова гарантированно принадлежит минимальной взвешенной триангуляции. Если рёбра, найденные таким образом, образуют связный граф на всех точках, то оставшиеся рёбра минимальной взвешенной триангуляции могут быть найдены за полиномиальное время с помощью динамического программирования. Однако, в общем случае, задача минимальной взвешенной триангуляции является NP-трудной задачей и подмножество рёбер, найденных таким образом, может не быть связнымШаблон:SfnШаблон:Sfn.

<math>\beta</math>-остова были также применены в машинном обучении для задач геометрической классификацииШаблон:SfnШаблон:Sfn и в беспроводных ad-hoc-сетях в качестве механизма контроля сложности сети путём выбора подмножества пар беспроводных станций, которые могут общаться друг с другомШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Бета-остов&oldid=9175432