Геометрический ключ

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

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

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

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

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

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

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

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

Тета-график

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

Жадный гаечный ключ

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

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

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

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

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

Наилучшая верхняя граница, известная для евклидовой триангуляции Делоне, состоит в том, что это $1.998$ -spanner для его вершин. ^[8]Нижняя граница увеличена с ${{\pi }/2}$ чуть больше этого, до 1,5846. ^[9]

Хорошо разделяемое парное разложение

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

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

Ссылки

^ Нарасимхан, Гири; Смид, Михил (2007), Geometric Spanner Networks , Cambridge University Press , ISBN 978-0-521-81513-0 .
^ Чу, Л. Пол (1986), «Существует плоский граф, почти такой же хороший, как полный граф», Proc. 2-й ежегодный симпозиум по вычислительной геометрии , стр. 169–177, doi : 10.1145/10515.10534 , S2CID 42010166 .
^ Кляйн, Рольф; Куц, Мартин (2007), «Вычисление геометрических графов минимального расширения NP-сложно», Кауфманн, Майкл; Вагнер, Доротея (ред.), Proc. 14-й Международный симпозиум по рисованию графов, Карлсруэ, Германия, 2006 г. , Конспекты лекций по информатике , том. 4372, Springer Verlag , стр. 196–207, doi : 10.1007/978-3-540-70904-6 , ISBN. 978-3-540-70903-9 .
^ Дас, Гаутам (1990), Схемы аппроксимации в вычислительной геометрии (докторская диссертация), Университет Висконсина-Мэдисона, OCLC 22935858
^ Альтёфер, Инго ; Дас, Гаутама ; Добкин, Дэвид ; Джозеф, Дебора (1990), «Генерация разреженных ключей для взвешенных графов» , SWAT 90 , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 26–37, CiteSeerX 10.1.1.158.2241 , doi : 10.1007/3-540-52846- 6_75 , ISBN 978-3-540-52846-3 , получено 16 марта 2021 г.
^ Альтёфер, Инго ; Дас, Гаутама ; Добкин, Дэвид ; Джозеф, Дебора ; Соарес, Хосе (1993), «О редких ключах взвешенных графов», Discrete & Computational Geometry , 9 (1): 81–100, doi : 10.1007/BF02189308 , MR 1184695
^ Бозе, П. ; Карми, П.; Фарши, М.; Махешвари, А.; Смид, М. (2010), «Вычисление жадного гаечного ключа за почти квадратичное время», Algorithmica , 58 (3): 711–729, doi : 10.1007/s00453-009-9293-4 , S2CID 8068690
^ Ся, Ге (2013), «Коэффициент растяжения триангуляции Делоне меньше 1,998», SIAM Journal on Computing , 42 (4): 1620–1659, arXiv : 1103.4361 , doi : 10.1137/110832458 , MR 3082502 , S2CID 6646 528
^ Бозе, Просенджит ; Деврой, Люк; Леффлер, Мартен; Снойинк, Джек; Верма, Вишал (2009): «Коэффициент охвата триангуляции Делоне больше, чем ${\pi /2}$ », Канадская конференция по вычислительной геометрии (PDF) , Ванкувер, стр. 165–167. {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Каллахан, ПБ; Косараджу, С.Р. (январь 1995 г.), "Разложение многомерных множеств точек с приложениями к $k$ -ближайшие соседи и $n$ Ботениальные поля -тела», Журнал ACM , 42 (1): 67–90, doi : 10.1145/200836.200853 , S2CID 1818562

[ns-1] Нарасимхан, Гири; Смид, Михил (2007), Geometric Spanner Networks , Cambridge University Press , ISBN 978-0-521-81513-0 .

[chew-2] Чу, Л. Пол (1986), «Существует плоский граф, почти такой же хороший, как полный граф», Proc. 2-й ежегодный симпозиум по вычислительной геометрии , стр. 169–177, doi : 10.1145/10515.10534 , S2CID 42010166 .

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

[gd1-4] Дас, Гаутам (1990), Схемы аппроксимации в вычислительной геометрии (докторская диссертация), Университет Висконсина-Мэдисона, OCLC 22935858

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

[ad3s-6] Альтёфер, Инго ; Дас, Гаутама ; Добкин, Дэвид ; Джозеф, Дебора ; Соарес, Хосе (1993), «О редких ключах взвешенных графов», Discrete & Computational Geometry , 9 (1): 81–100, doi : 10.1007/BF02189308 , MR 1184695

[7] Бозе, П. ; Карми, П.; Фарши, М.; Махешвари, А.; Смид, М. (2010), «Вычисление жадного гаечного ключа за почти квадратичное время», Algorithmica , 58 (3): 711–729, doi : 10.1007/s00453-009-9293-4 , S2CID 8068690

[8] Ся, Ге (2013), «Коэффициент растяжения триангуляции Делоне меньше 1,998», SIAM Journal on Computing , 42 (4): 1620–1659, arXiv : 1103.4361 , doi : 10.1137/110832458 , MR 3082502 , S2CID 6646 528

[9] Бозе, Просенджит ; Деврой, Люк; Леффлер, Мартен; Снойинк, Джек; Верма, Вишал (2009): «Коэффициент охвата триангуляции Делоне больше, чем ${\pi /2}$ », Канадская конференция по вычислительной геометрии (PDF) , Ванкувер, стр. 165–167. {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]