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

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

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

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

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

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

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

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

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

Тета-график

Основная статья: Тета-график

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

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

Основная статья: Жадный геометрический ключ

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

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

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

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

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

Лучшая верхняя граница, известная для евклидова Триангуляция Делоне в том, что это ${displaystyle {(4{sqrt {3}}/9)pi }approx 2.418}$гаечный ключ для его вершин.^[6] Нижняя граница увеличена с ${displaystyle {{pi }/2}}$ чуть выше 1,5846.^[7]

Разложение хорошо разделенных пар

Основная статья: Разложение хорошо разделенных пар

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

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

Рекомендации

1. Нарасимхан, Гири; Smid, Michiel (2007), Геометрические гаечные сети, Издательство Кембриджского университета, ISBN  978-0-521-81513-0.
2. Чу, Л. Пол (1986), «Плоский граф почти так же хорош, как и полный граф», Proc. 2-й ежегодный симпозиум по вычислительной геометрии, стр. 169–177, Дои:10.1145/10515.10534.
3. Кляйн, Рольф; Куц, Мартин (2007), «Вычисление геометрических графов с минимальным расширением является NP-трудным», у Кауфманна, Михаэля; Вагнер, Доротея (ред.), Proc. 14-й Международный симпозиум по графическому рисованию, Карлсруэ, Германия, 2006 г., Конспект лекций по информатике, 4372, Springer Verlag, стр. 196–207, Дои:10.1007/978-3-540-70904-6, ISBN  978-3-540-70903-9.
4. Althöfer, I .; Das, G .; Добкин, Д. П.; Джозеф, Д.; Соарес, Дж. (1993), "О разреженных ключах взвешенных графов", Дискретная и вычислительная геометрия, 9: 81–100, Дои:10.1007 / bf02189308
5. Бозе, П.; Carmi, P .; Фарши, М .; Махешвари, А .; Смид, М. (2010), "Вычисление жадного гаечного ключа за почти квадратичное время", Алгоритмика, 58 (3): 711–729, Дои:10.1007 / s00453-009-9293-4
6. Keil, J.M .; Гутвин, К. А. (1992), "Классы графов, которые аппроксимируют полный евклидов граф", Дискретная и вычислительная геометрия, 7 (1): 13–28, Дои:10.1007 / BF02187821.
7. Бозе, Просенджит; Деврой, Люк; Лёффлер, Маартен; Snoeyink, Джек; Верма, Вишал (2009), Коэффициент охвата триангуляции Делоне больше, чем ${displaystyle {pi /2}}$ (PDF), Ванкувер, стр. 165–167.
8. Каллахан, П. Б .; Косараджу, С. (Январь 1995 г.), "Разложение многомерных точечных множеств с приложениями к ${displaystyle k}$Ближайшие соседи и ${displaystyle n}$-оботенциальные поля тела ", Журнал ACM, 42 (1): 67–90, Дои:10.1145/200836.200853