Геометрический ключ - 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} примерно 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}$ выбрав соответствующий параметр разделения хорошо разделенной пары.

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