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

Геометрический остов (англ. 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)}$.

Примечания

1. Narasimhan, Smid, 2007.
2. Chew, 1986, с. 169–177.
3. Klein, Kutz, 2007, с. 196–207.
4. Althöfer, Das, Dobkin, Joseph, Soares, 1993, с. 81–100.
5. Bose, Carmi, Farshi, Maheshwari, Smid, 2010, с. 711–729.
6. Keil, Gutwin, 1992, с. 13–28.
7. Bose, Devroye, Loeffler, Snoeyink, Verma, 2009, с. 165–167.
8. Callahan, Kosaraju, 1995, с. 67–90.
9. Callahan, Kosaraju, 1993, с. 291–300.

Литература

• L. Paul Chew. There is a planar graph almost as good as the complete graph // Proc. 2nd Annual Symposium on Computational Geometry. — 1986. — doi:10.1145/10515.10534.
• Rolf Klein, Martin Kutz. Computing Geometric Minimum-Dilation Graphs is NP-Hard // Proc. 14th International Symposium in Graph Drawing, Karlsruhe, Germany, 2006 / Michael Kaufmann, Dorothea Wagner. — Springer Verlag, 2007. — Т. 4372. — (Lecture Notes in Computer Science). — ISBN 978-3-540-70903-9. — doi:10.1007/978-3-540-70904-6.
• Paul B. Callahan, S. Rao Kosaraju. Faster Algorithms for Some Geometric Graph Problems in Higher Dimensions // Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. — Austin, Texas, USA: Society for Industrial and Applied Mathematics, 1993. — (SODA '93). — ISBN 0-89871-313-7. — doi:10.1145/313559.313777.
• Althöfer I., Das G., Dobkin D. P., Joseph D., Soares J. On sparse spanners of weighted graphs. // Discrete & Computational Geometry. — 1993. — Т. 9. — doi:10.1007/bf02189308.
• Bose P., Carmi P., Farshi M., Maheshwari A., Smid. M. Computing the greedy spanner in near-quadratic time // Algorithmica. — 2010. — Т. 58. — doi:10.1007/s00453-009-9293-4.
• Keil J. M., Gutwin C. A. Classes of graphs which approximate the complete Euclidean graph // Discrete and Computational Geometry. — 1992. — Т. 7, вып. 1. — doi:10.1007/BF02187821.
• Prosenjit Bose, Luc Devroye, Maarten Loeffler, Jack Snoeyink, Vishal Verma. The spanning ratio of the Delaunay triangulation is greater than ${\displaystyle \scriptstyle {\pi /2}}$ // Canadian Conference on Computational Geometry. — Vancouver, 2009.
• Callahan P. B., Kosaraju S. R. A Decomposition of Multidimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields // Journal of the ACM. — 1995. — Январь (т. 42, вып. 1). — doi:10.1145/200836.200853.
• Giri Narasimhan, Michiel Smid. Geometric Spanner Networks. — Cambridge University Press, 2007. — ISBN 0-521-81513-4.