Геометрический остов

Геометрический остов (Шаблон:Lang-en) или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется Шаблон:Не переведено 5 остоваШаблон:Sfn.

В вычислительной геометрии концепцию первым обсуждал Л.П. Чу в 1986Шаблон:Sfn, хотя термин «spanner» (остов) в статье упомянут не был.

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

Остовы могут быть использованы в вычислительной геометрии для решения некоторых Шаблон:Не переведено 5. Они находят также приложения в других областях, таких как Шаблон:Не переведено 5, в коммуникационных сетях — надёжность сети, оптимизация роуминга в мобильных сетях и т.д..

Различные остовы и меры качества

Существуют различные меры, используемые для анализа качества остовов. Наиболее распространёнными мерами являются число рёбер, общий вес и максимальная степень вершин. Асимптотически оптимальные значения для этих мер —$O(n)$ рёбер, $O(MST)$ для общего веса и $O(1)$ для максимальной степени (здесь MST означает вес минимального остовного дерева).

Известно, что поиск остова на евклидовой плоскости с минимальным растяжением на n точках с максимум m рёбрами является NP-трудной задачейШаблон:Sfn.

Есть много алгоритмов, которые хорошо ведут себя при различных мерах качества. Быстрые алгоритмы включают остовную Шаблон:Не переведено 5 (Шаблон:Lang-en, WSPD) и тета-графы, которые строят остовы с линейным числом рёбер за время $O(n\log n)$. Если требуются лучшие веса и степени вершин, жадный остов вычисляется почти за квадратичное время.

Тета-граф

Шаблон:Основная статья Тета-граф или $\mathrm{\Theta }$-граф принадлежит семейству основанных на конусе остовов. Основной метод построения заключается в разделении пространства вокруг каждой вершины на множество конусов (плоский конус — это два луча, то есть угол), которые разделяют оставшиеся вершины графа. Подобно графам Яо, $\mathrm{\Theta }$-граф содержит максимум по одному ребру для конуса. Подход отличается в способе выбора рёбер. В то время как графы Яо выбирают ближайшую вершину согласно метрическому расстоянию в графе, $\mathrm{\Theta }$-граф определяет фиксированный луч, содержащийся в каждом конусе (обычно биссектриса конуса) и выбираются ближайшие соседи (то есть имеющие наименьшее расстояние до луча).

Жадный остов

Шаблон:Основная статья Жадный остов или жадный граф определяется как граф, получающийся путём многократного добавления ребра между точками, не имеющими t-пути. Алгоритмы вычисления этого графа упоминаются как алгоритмы жадного остова. Из построения тривиально следует, что жадные графы являются t-остовами.

Жадный остов открыли в 1989 независимо АльтхёферШаблон:Sfn и Берн (не опубликовано).

Жадный остов достигает асимптотически оптимальное число рёбер, общий вес и максимальную степень вершины и даёт лучшие величины меры на практике. Он может быть построен за время $O(n^2\log n)$ с использованием пространства $O(n^2)$Шаблон:Sfn.

Триангуляция Делоне

Главным результатом Чу было то, что для множества точек на плоскости существует триангуляция этих наборов точек, такая, что для любых двух точек существует путь вдоль рёбер триангуляции с длиной, не превосходящей $\sqrt{1}0$ евклидова расстояния между двумя точками. Результат был использован в планировании движения для поиска приемлемого приближения кратчайшего пути среди препятствий.

Лучшая верхняя известная граница для триангуляции Делоне равна $(4\sqrt{3}/9)\pi \approx 2,418$-остова для его вершинШаблон:Sfn. Нижняя граница была увеличена с $\pi /2$ до 1,5846Шаблон:Sfn.

Вполне разделенная декомпозиция пар

Шаблон:Основная статья Остов может быть построен из Шаблон:Не переведено 5 следующим образом. Строим граф с набором точек $S$ в качестве вершин и для каждой пары $\{A,B\}$ в WSPD добавляем ребро из произвольной точки $a\in A$ в произвольную точку $b\in B$. Заметим, что получающийся граф имеет линейное число рёбер, поскольку WSPD имеет линейное число парШаблон:Sfn.

Нам нужны эти два Шаблон:Не переведено 5:

Лемма 1: Пусть $\{A,B\}$ будет вполне разделенной декомпозицией пар по отношению к $s$. Пусть $p,p^{\prime }\in A$ и $q\in B$. Тогда $|p{p}^{\prime }|⩽(2/s)|pq|$.

Лемма 2: Пусть $\{A,B\}$ будет вполне разделенной декомпозицией пар по отношению к $s$. Пусть $p,p^{\prime }\in A$ и $q,q^{\prime }\in B$. Тогда, $|p^{\prime }{q}^{\prime }|⩽(1+4/s)|pq|$.

Пусть $\{A,B\}$ будет вполне разделенной декомпозицией пар по отношению к $s$ в WSPD. Пусть $[a,b]$ будет ребром, соединяющим $A$ с $B$. Пусть есть точка $p\in A$ и точка $q\in B$. По определению WSPD достаточно проверить, что есть $t$-остовной путь, или $t$-путь для краткости, между $p$ и $q$, который обозначим $P_{pq}$. Обозначим длину пути $P_{pq}$ через $|P_{pq}|$.

Предположим, что есть $t$-путь между любой парой точек с расстоянием, меньшим или равным $|pq|$ и $s>2$. Из неравенства треугольника, предположений и факта, что $|pa|⩽(2/s)|pq|\Rightarrow |pa|<|pq|$ и $|bq|⩽(2/s)|pq|\Rightarrow |bq|<|pq|$ согласно Лемме 1 мы имеем:

$|P_{pq}|⩽t|pa|+|ab|+t|bq|$

Из леммы 1 и 2 мы получаем:

$\begin{array}{cc}|P_{pq}|& ⩽t(2/s)|pq|+(1+4/s)|pq|+t(2/s)|pq|\\ & =t(4/s)|pq|+(1+4/s)|pq|\\ & =\left(\frac{4t+4}{s}\right)|pq|+|pq|\\ & =(\frac{4(t+1)}{s}+1)|pq|\end{array}$

Так что:

$\begin{array}{cc}t& =\frac{4(t+1)}{s}+1\\ t-1& =\frac{4(t+1)}{s}\\ s(t-1)& =4(t+1)\\ s(t-1)-4(t+1)& =0\\ st-s-4t-4& =0\\ t(s-4)-s-4& =0\\ t(s-4)& =s+4\\ t& =\frac{s+4}{s-4}\end{array}$

И так, если $t=(s+4)/(s-4)$ и $s>4$, то мы имеем $t$-остов для набора точек $S$. Шаблон:Collapse bottom

Согласно доказательству можно иметь произвольное значение для $t$ путём выражения $s$ из $t=(s+4)/(s-4)$, что даёт $s=4(t+1)/(t-1)$.

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга