Геометрический гаечный ключ

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

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

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

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

Различные ключи и меры качества [ править ]

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

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

Существует множество универсальных алгоритмов, которые превосходят по разным показателям качества. Быстрые алгоритмы включают гаечный ключ WSPD и граф Theta, которые строят гаечные ключи с линейным числом ребер во времени. Если требуются лучший вес и степень вершины, жадный гаечный ключ можно вычислить почти за квадратичное время. ${\ Displaystyle О (п \ журнал п)}$

Тета-график [ править ]

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

Жадный гаечный ключ [ править ]

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

Жадный гаечный ключ был впервые описан в докторской диссертации Гаутама Даса ^[4], статье конференции ^[5] и последующей журнальной статье Инго Альтхёфера и др. ^[6] . Эти источники также приписывают Маршаллу Берну (неопубликовано) независимое открытие той же конструкции.

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

Триангуляция Делоне [ править ]

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

Лучшая верхняя граница, известная для евклидовой триангуляции Делоне, состоит в том, что она является -разъемом для своих вершин. ^[8] Нижняя граница была увеличена с почти до 1,5846. ^[9] ${(4{\sqrt {3}}/9)\pi }\approx 2.418$ ${{\pi }/2}$

Разложение хорошо разделенных пар [ править ]

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

Можно получить произвольное значение для , выбрав соответствующий параметр разделения хорошо разделенной парной декомпозиции. $t$

Ссылки [ править ]

^ Нарасимхан, Гири; Smid, Michiel (2007), Геометрические сети гаечного ключа , Cambridge University Press , ISBN 978-0-521-81513-0.
^ Чу, Л. Пол (1986), «Плоский граф почти так же хорош, как и полный граф», Proc. 2 - й ежегодный симпозиум по вычислительной геометрии . С. 169-177, DOI : 10,1145 / 10515,10534.
^ Кляйн, Рольф; Куц, Мартин (2007), «Вычисление геометрических графов с минимальным расширением является NP-трудным», у Кауфманна, Михаэля; Вагнер, Доротея (ред.), Proc. 14 - й Международный симпозиум по Graph Рисованные, Карлсруэ, Германия, 2006 , Lecture Notes в области компьютерных наук , 4372 , Springer Verlag ., Стр 196-207, DOI : 10.1007 / 978-3-540-70904-6 , ISBN 978-3-540-70903-9.
^ Дас, Гаутам . Аппроксимационные схемы в вычислительной геометрии . OCLC 22935858 .
^ Альтхёфер, Инго ; Дас, Гаутам ; Добкин, Дэвид ; Джозеф, Дебора (1990), «Генерация разреженных гаечных ключей для взвешенных графов» , SWAT 90 , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 26–37, ISBN 978-3-540-52846-3, получено 16 марта 2021 г.
^ Альтхёфер, Инго ; Дас, Гаутам ; Добкин, Дэвид ; Иосиф, Девора ; Soares, Хосе (1993), "О разреженных гаечных взвешенных графах", дискретная и вычислительная геометрия , 9 (1): 81-100, DOI : 10.1007 / BF02189308 , MR 1184695
^ Бозе, П .; Carmi, P .; Фарши, М .; Maheshwari, A .; Шмид, М. (2010), "Вычисление жадного гаечного ключа в ближнем квадратичное время.", Algorithmica , 58 (3): 711-729, DOI : 10.1007 / s00453-009-9293-4
^ Кейл, JM; Гутвин, Калифорния (1992), «Классы графов, которые аппроксимируют полный евклидов граф», Дискретная и вычислительная геометрия , 7 (1): 13–28, DOI : 10.1007 / BF02187821.
^ Бозе, Просенджит ; Деврой, Люк; Лёффлер, Маартен; Snoeyink, Джек; Верма, Вишал (2009), Коэффициент охвата триангуляции Делоне больше, чем (PDF) , Ванкувер, стр. 165–167. π / 2 {\displaystyle {\pi /2}}
^ Каллахан, ПБ; Косараджу, С.Р. (январь 1995 г.), «Разложение многомерных точечных множеств с приложениями к -ближайшим-соседям и -телоботенциальным полям», журнал ACM , 42 (1): 67–90, doi : 10.1145 / 200836.200853 $k$ $n$

[1] Нарасимхан, Гири; Smid, Michiel (2007), Геометрические сети гаечного ключа , Cambridge University Press , ISBN 978-0-521-81513-0.

[2] Чу, Л. Пол (1986), «Плоский граф почти так же хорош, как и полный граф», Proc. 2 - й ежегодный симпозиум по вычислительной геометрии . С. 169-177, DOI : 10,1145 / 10515,10534.

[3] Кляйн, Рольф; Куц, Мартин (2007), «Вычисление геометрических графов с минимальным расширением является NP-трудным», у Кауфманна, Михаэля; Вагнер, Доротея (ред.), Proc. 14 - й Международный симпозиум по Graph Рисованные, Карлсруэ, Германия, 2006 , Lecture Notes в области компьютерных наук , 4372 , Springer Verlag ., Стр 196-207, DOI : 10.1007 / 978-3-540-70904-6 , ISBN 978-3-540-70903-9.

[gd1-4] Дас, Гаутам . Аппроксимационные схемы в вычислительной геометрии . OCLC 22935858 .

[ad2j-5] Альтхёфер, Инго ; Дас, Гаутам ; Добкин, Дэвид ; Джозеф, Дебора (1990), «Генерация разреженных гаечных ключей для взвешенных графов» , SWAT 90 , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 26–37, ISBN 978-3-540-52846-3, получено 16 марта 2021 г.

[ad3s-6] Альтхёфер, Инго ; Дас, Гаутам ; Добкин, Дэвид ; Иосиф, Девора ; Soares, Хосе (1993), "О разреженных гаечных взвешенных графах", дискретная и вычислительная геометрия , 9 (1): 81-100, DOI : 10.1007 / BF02189308 , MR 1184695

[7] Бозе, П .; Carmi, P .; Фарши, М .; Maheshwari, A .; Шмид, М. (2010), "Вычисление жадного гаечного ключа в ближнем квадратичное время.", Algorithmica , 58 (3): 711-729, DOI : 10.1007 / s00453-009-9293-4

[8] Кейл, JM; Гутвин, Калифорния (1992), «Классы графов, которые аппроксимируют полный евклидов граф», Дискретная и вычислительная геометрия , 7 (1): 13–28, DOI : 10.1007 / BF02187821.

[9] Бозе, Просенджит ; Деврой, Люк; Лёффлер, Маартен; Snoeyink, Джек; Верма, Вишал (2009), Коэффициент охвата триангуляции Делоне больше, чем (PDF) , Ванкувер, стр. 165–167. π / 2 {\displaystyle {\pi /2}}

[callahan-kosaraju-10] Каллахан, ПБ; Косараджу, С.Р. (январь 1995 г.), «Разложение многомерных точечных множеств с приложениями к -ближайшим-соседям и -телоботенциальным полям», журнал ACM , 42 (1): 67–90, doi : 10.1145 / 200836.200853 $k$ $n$

[1]