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

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

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

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

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

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

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

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

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

Тета-граф

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

Жадный остов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Так что:

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

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

Примечания

Литература

  • 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 // 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.