Жадный геометрический гаечный ключ - Greedy geometric spanner

Жадный геометрический гаечный ключ на 100 случайных точек с коэффициентом растяжения т = 2

Жадный геометрический гаечный ключ из одинаковых точек с коэффициентом растяжения т = 1.1

В вычислительная геометрия, а жадный геометрический гаечный ключ является неориентированный граф чьи вершины представляют точки в Евклидово пространство, и ребра которого выбираются жадный алгоритм сделать кратчайший путь расстояния в графе (с ребрами, взвешенными по длине) приблизительно равны Евклидовы расстояния между парами точек. Конструкция жадных гаечных ключей была впервые опубликована Инго Альтхёфер и другие. в 1993 г ​​.; в их статье также приписывается Маршаллу Берну (неопубликовано) независимое открытие той же конструкции.^[1]

Жадные геометрические гаечные ключи ограничили степень, линейное общее количество ребер и общий вес, близкий к весу Евклидово минимальное остовное дерево. Хотя известные методы строительства для них медленные, быстрые аппроксимационные алгоритмы с подобными свойствами известны.^[2]

Строительство

Жадный геометрический гаечный ключ определяется из ввода, состоящего из набора точек и параметра ${\displaystyle t\geq 1}$. Цель состоит в том, чтобы построить граф, кратчайшие пути которого не превышают ${\displaystyle t}$ умноженное на геометрические расстояния между парами точек. Он может быть построен жадный алгоритм который добавляет к графу ребра по одному, начиная с безреберный граф с точками в качестве вершин. Все пары точек рассматриваются в отсортированном (возрастающем) порядке по расстояниям, начиная с ближайшая пара. Для каждой пары ${\displaystyle (u,v)}$ точек, алгоритм проверяет, содержит ли уже построенный граф путь из ${\displaystyle u}$ к ${\displaystyle v}$ с длиной не более ${\displaystyle t\cdot d(u,v)}$. Если нет, край ${\displaystyle uv}$ с длиной ${\displaystyle d(u,v)}$ добавляется к графу. По построению результирующий граф является геометрический гаечный ключ с коэффициент растяжения в большинстве ${\displaystyle t}$.^[1]

Наивная реализация этого метода потребует времени ${\displaystyle O(n^{3}\log n)}$ на входах с ${\displaystyle n}$ точки. Это потому, что соображения для каждого из ${\displaystyle O(n^{2})}$ пары точек включают экземпляр Алгоритм Дейкстры найти кратчайший путь в графе с ${\displaystyle O(n)}$ края. Оно использует ${\displaystyle O(n^{2})}$ пространство для хранения отсортированного списка пар точек. Более тщательные алгоритмы могут построить тот же график за время ${\displaystyle O(n^{2}\log n)}$,^[3] или в космосе ${\displaystyle O(n)}$.^[4]Конструкция варианта жадного гаечного ключа, использующего кластеризацию графов для быстрой аппроксимации расстояний между графами, выполняется во времени. ${\displaystyle O(n\log n)}$ в евклидовых пространствах любой ограниченной размерности, и может производить гаечные ключи с (приблизительно) теми же свойствами, что и жадные гаечные ключи.^[5][6] Тот же метод можно распространить на пространства с ограниченными удвоение размера.^[2]

Характеристики

Та же жадная конструкция производит гаечные ключи произвольной формы. метрические пространства, но в евклидовом пространстве он обладает хорошими свойствами, некоторые из которых не выполняются в целом.^[2]

Жадный геометрический гаечный ключ в любом метрическом пространстве всегда содержит минимальное остовное дерево входных данных, поскольку алгоритм жадного построения следует тому же порядку вставки ребер, что и Алгоритм Краскала для минимальных остовных деревьев. Если алгоритм жадного гаечного ключа и алгоритм Крускала запускаются параллельно, рассматривая одни и те же пары вершин в одном порядке, каждое ребро, добавленное алгоритмом Крускала, также будет добавлено алгоритмом жадного гаечного ключа, потому что конечные точки ребра еще не будут соединены дорогой. В предельном случае, когда ${\displaystyle t}$ достаточно большой (например, ${\displaystyle t>n}$, куда ${\displaystyle n}$ - количество вершин в графе) два алгоритма дают одинаковый результат.^[1]

В евклидовых пространствах ограниченной размерности для любой постоянной ${\displaystyle t}$, жадный геометрический ${\displaystyle t}$гаечные ключи на наборах ${\displaystyle n}$ точки ограничены степень, подразумевая, что у них также есть ${\displaystyle O(n)}$ края.^[7][8][5] Это свойство не распространяется даже на метрические пространства с хорошим поведением: существуют пространства с ограниченными удвоение размера где жадный гаечный ключ имеет неограниченную степень вершины.^[2][9][10] Однако в таких пространствах количество ребер по-прежнему равно ${\displaystyle O(n)}$.^[2]

Жадные геометрические гаечные ключи в евклидовых пространствах ограниченной размерности также имеют общий вес не более чем на постоянную величину, умноженную на общий вес Евклидово минимальное остовное дерево.^[7][8][5]Это свойство сохраняется в пространствах ограниченной удвоенной размерности.^[2]

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

1. Альтхёфер, Инго; Дас, Гаутам; Добкин, Давид; Джозеф, Дебора; Соарес, Хосе (1993), "О разреженных ключах взвешенных графов", Дискретная и вычислительная геометрия, 9 (1): 81–100, Дои:10.1007 / BF02189308, МИСТЕР  1184695
2. Фильцер, Арнольд; Соломон, Шэй, "Жадный гаечный ключ экзистенциально оптимален", Материалы ACM 2016 г. Симпозиум по принципам распределенных вычислений (PODC '16), Нью-Йорк, Нью-Йорк, США: ACM, стр. 9–17, arXiv:1605.06852, Дои:10.1145/2933057.2933114
3. Бозе, Просенджит; Карми, Пас; Фарши, Мохаммад; Махешвари, Анил; Smid, Michiel (2010), "Вычисление жадного гаечного ключа за почти квадратичное время", Алгоритмика, 58 (3): 711–729, Дои:10.1007 / s00453-009-9293-4, МИСТЕР  2672477
4. Alewijnse, Sander P.A .; Баутс, Quirijn W .; ten Brink, Alex P .; Бучин, Кевин (2015), "Вычисление жадного гаечного ключа в линейном пространстве", Алгоритмика, 73 (3): 589–606, arXiv:1306.4919, Дои:10.1007 / s00453-015-0001-2, МИСТЕР  3411749
5. Дас, Гаутам; Нарасимхан, Гири (1997), "Быстрый алгоритм построения разреженных евклидовых гаечных ключей", Международный журнал вычислительной геометрии и приложений, 7 (4): 297–315, Дои:10.1142 / S0218195997000193, МИСТЕР  1460840
6. Гудмундссон, Иоахим; Левкопулос, Христос; Нарасимхан, Гири (2002), «Быстрые жадные алгоритмы для построения разреженных геометрических ключей», SIAM Журнал по вычислениям, 31 (5): 1479–1500, Дои:10.1137 / S0097539700382947, МИСТЕР  1936655
7. Чандра, Барун; Дас, Гаутам; Нарасимхан, Гири; Соарес, Хосе (1995), "Новые результаты разреженности на гаечных ключах графа", Международный журнал вычислительной геометрии и приложений, 5 (1–2): 125–144, Дои:10.1142 / S0218195995000088, МИСТЕР  1331179
8. Дас, Гаутам; Хеффернан, Пол; Нарасимхан, Гири (1993), "Оптимально разреженные гаечные ключи в 3-мерном евклидовом пространстве", Материалы девятого ежегодного Симпозиум по вычислительной геометрии (SoCG '93), Нью-Йорк, Нью-Йорк, США: ACM, стр. 53–62, Дои:10.1145/160985.160998
9. Хар-Пелед, Сариэль; Мендель, Манор (2006), "Быстрое построение сетей в низкоразмерных метриках и их приложениях", SIAM Журнал по вычислениям, 35 (5): 1148–1184, Дои:10.1137 / S0097539704446281, МИСТЕР  2217141
10. Смид, Михил Х. М. (2009), "Свойство слабой щели в метрических пространствах ограниченной удвоенной размерности", в Альберс, Сюзанна; Альт, Гельмут; Нэхер, Стефан (ред.), Эффективные алгоритмы: эссе, посвященные Курту Мельхорну по случаю его 60-летия, Конспект лекций по информатике, 5760, Springer, стр. 275–289, Дои:10.1007/978-3-642-03456-5_19