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

Взвешенный неориентированный граф с графовыми расстояниями, линейно ограниченными относительно евклидовых расстояний

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

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

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

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

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

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

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

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

Тета-график

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

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Нарасимхан, Гири; Смид, Михил (2007), Геометрические остовные сети , Cambridge University Press , ISBN 978-0-521-81513-0.
2. Чу, Л. Пол (1986), «Существует планарный граф, почти такой же хороший, как и полный граф», Труды 2-го ежегодного симпозиума по вычислительной геометрии , стр. 169–177, doi :10.1145/10515.10534, S2CID  42010166.
3. Кляйн, Рольф; Куц, Мартин (2007), «Вычисление геометрических графов с минимальным растяжением является NP-трудным», в Кауфманн, Михаэль; Вагнер, Доротея (ред.), Proc. 14th International Symposium in Graph Drawing, Карлсруэ, Германия, 2006 , Lecture Notes in Computer Science , т. 4372, Springer Verlag , стр. 196–207, doi :10.1007/978-3-540-70904-6, ISBN 978-3-540-70903-9.
4. Дас, Гаутам (1990), Схемы аппроксимации в вычислительной геометрии (кандидатская диссертация), Университет Висконсин-Мэдисон, OCLC  22935858
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 г.
6. Альтхёфер, Инго ; Дас, Гаутам ; Добкин, Дэвид ; Джозеф, Дебора ; Соарес, Хосе (1993), «О разреженных остовах взвешенных графов», Дискретная и вычислительная геометрия , 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  6646528
9. Бозе, Просенджит ; Девройе, Люк; Леффлер, Маартен; Сноейинк, Джек; Верма, Вишал (2009), «Коэффициент охвата триангуляции Делоне больше », Канадская конференция по вычислительной геометрии (PDF) , Ванкувер, стр. 165–167 ${\displaystyle {\pi /2}}${{citation}}: CS1 maint: location missing publisher (link)
10. Каллахан, П. Б.; Косараджу, С. Р. (январь 1995 г.), «Разложение многомерных точечных множеств с приложениями к ближайшим соседям и ботенциальным полям», Журнал ACM , 42 (1): 67–90, doi : 10.1145/200836.200853 , S2CID  1818562 ${\displaystyle k}$ ${\displaystyle n}$