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

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

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

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

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

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

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

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

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

Тета-граф

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

Жадный остов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ |P_{pq}| \leqslant t|pa| + |ab| + t|bq| }[/math]

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

[math]\displaystyle{ \begin{align} |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{align} }[/math]

Так что:

[math]\displaystyle{ \begin{align} 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{align} }[/math]

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

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

Примечания

↑ Narasimhan, Smid, 2007.
↑ Chew, 1986, с. 169–177.
↑ Klein, Kutz, 2007, с. 196–207.
↑ Althöfer, Das, Dobkin, Joseph, Soares, 1993, с. 81–100.
↑ Bose, Carmi, Farshi, Maheshwari, Smid, 2010, с. 711–729.
↑ Keil, Gutwin, 1992, с. 13–28.
↑ Bose, Devroye, Loeffler, Snoeyink, Verma, 2009, с. 165–167.
↑ Callahan, Kosaraju, 1995, с. 67–90.
↑ 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 [math]\displaystyle{ \scriptstyle{\pi/2} }[/math] // 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.

[_2f5a4f750311f4ab-1] Narasimhan, Smid, 2007.

[_c5ebc74cea908310-2] Chew, 1986, с. 169–177.

[_414942596897648d-3] Klein, Kutz, 2007, с. 196–207.

[_6efde14b849301c8-4] Althöfer, Das, Dobkin, Joseph, Soares, 1993, с. 81–100.

[_2bacf3bb0c7db106-5] Bose, Carmi, Farshi, Maheshwari, Smid, 2010, с. 711–729.

[_741217913928a6b0-6] Keil, Gutwin, 1992, с. 13–28.

[_df2b5061725df2f2-7] Bose, Devroye, Loeffler, Snoeyink, Verma, 2009, с. 165–167.

[_44bb70caf1763bee-8] Callahan, Kosaraju, 1995, с. 67–90.

[_6aba3e5afc262431-9] Callahan, Kosaraju, 1993, с. 291–300.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]