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

Геометрический остов (англ. geometric spanner) или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется коэффициентом растяжения^[англ.] остова^[1].

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

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

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

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

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

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

Есть много алгоритмов, которые хорошо ведут себя при различных мерах качества. Быстрые алгоритмы включают остовную вполне разделенную декомпозицию пар^[англ.] (англ. Well-separated pair decomposition, WSPD) и тета-графы, которые строят остовы с линейным числом рёбер за время ${\displaystyle O(n\log n)}$. Если требуются лучшие веса и степени вершин, жадный остов вычисляется почти за квадратичное время.

Тета-граф

Основная статья: Тета-граф

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

Жадный остов

Основная статья: Жадный геометрический остов

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

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

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

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

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

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

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

Основная статья: Вполне разделенная декомпозиция пар

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

Доказательство корректности алгоритма ^[9]

Нам нужны эти два свойства WSPD^[англ.]:

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

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

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

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

${\displaystyle |P_{pq}|\leqslant t|pa|+|ab|+t|bq|}$

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

${\displaystyle {\begin{aligned}|P_{pq}|&\leqslant 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|\\&=\left({\frac {4(t+1)}{s}}+1\right)|pq|\end{aligned}}}$

Так что:

${\displaystyle {\begin{aligned}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{aligned}}}$

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

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