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

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

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

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

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

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

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

Есть много алгоритмов, которые хорошо ведут себя при различных мерах качества. Быстрые алгоритмы включают остовную  (, WSPD) и тета-графы, которые строят остовы с линейным числом рёбер за время . Если требуются лучшие веса и степени вершин, жадный остов вычисляется почти за квадратичное время.

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

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

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

Жадный остов достигает асимптотически оптимальное число рёбер, общий вес и максимальную степень вершины и даёт лучшие величины меры на практике.
Он может быть построен за время  с использованием пространства .

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

Лучшая верхняя известная граница для триангуляции Делоне равна -остова для его вершин.  
Нижняя граница была увеличена с  до 1,5846.

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

Остов может быть построен из  следующим образом. Строим граф с набором точек  в качестве вершин и для каждой пары  в WSPD добавляем ребро из произвольной точки  в произвольную точку . Заметим, что получающийся граф имеет линейное число рёбер, поскольку WSPD имеет линейное число пар.

Нам нужны эти два :

Лемма 1: Пусть  будет вполне разделенной декомпозицией пар по отношению к . Пусть  и . Тогда .

Лемма 2: Пусть  будет вполне разделенной декомпозицией пар по отношению к . Пусть  и . Тогда, .

Пусть  будет вполне разделенной декомпозицией пар по отношению к  в WSPD. Пусть  будет ребром, соединяющим  с . Пусть есть точка  и точка . По определению WSPD достаточно проверить, что есть -остовной путь, или -путь для краткости, между   и , который обозначим . Обозначим длину пути  через .

Предположим, что есть -путь между любой парой точек с расстоянием, меньшим или равным  и . Из неравенства треугольника, предположений и факта, что  и  согласно Лемме 1 мы имеем:

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

Так что:

И так, если  и , то мы имеем -остов для набора точек .

Согласно доказательству можно иметь произвольное значение для  путём выражения  из , что даёт .

Примечания

Литература

	

Геометрические алгоритмы
Геометрические графы