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

В вычислительной геометрии жадный геометрический гаечный ключ представляет собой неориентированный граф , расстояния которого аппроксимируют евклидовы расстояния между конечным набором точек в евклидовом пространстве . Вершины графа представляют эти точки. Края гаечного ключа выбираются с помощью жадного алгоритма , который включает ребро всякий раз, когда две его конечные точки не соединены коротким путем из более коротких ребер. Жадный гаечный ключ был впервые описан в докторской диссертации Гаутамы Даса. ^{[ 1 ]} и документ конференции ^{[ 2 ]} и последующая журнальная статья Инго Альтхёфера и др. ^{[ 3 ]} Эти источники также приписывают Маршаллу Берну (неопубликовано) независимое открытие той же конструкции.

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

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

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

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

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

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

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

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

Жадные геометрические остовы в евклидовых пространствах ограниченной размерности также имеют общий вес, не более чем в постоянный раз превышающий общий вес евклидова минимального остовного дерева . ^{[ 9 ]}^{[ 10 ]}^{[ 7 ]} Это свойство остается верным в пространствах ограниченной удвоенной размерности. ^{[ 4 ]}

Ссылки

^ Дас, Гаутам (1990), Схемы аппроксимации в вычислительной геометрии (докторская диссертация), Университет Висконсина, MR 2685391 , 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 г.
^ Jump up to: ^а ^б ^с Альтёфер, Инго ; Дас, Гаутама ; Добкин, Дэвид ; Джозеф, Дебора ; Соарес, Хосе (1993), «О редких ключах взвешенных графов», Discrete & Computational Geometry , 9 (1): 81–100, doi : 10.1007/BF02189308 , MR 1184695
^ Jump up to: ^а ^б ^с ^д ^и ^ж Фильцер, Арнольд; Соломон, Шей (2016), «Жадный гаечный ключ экзистенциально оптимален», Труды симпозиума ACM 2016 года по принципам распределенных вычислений (PODC '16) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 9–17, arXiv : 1605.06852 , дои : 10.1145/2933057.2933114 , S2CID 7229289
^ Бозе, Просенджит ; Карми, Пас; Фарши, Мохаммед; Махешвари, Анил; Смид, Михил (2010), «Вычисление жадного гаечного ключа за почти квадратичное время», Algorithmica , 58 (3): 711–729, doi : 10.1007/s00453-009-9293-4 , MR 2672477 , S2CID 8068690
^ Алевейнсе, Сандер, Пенсильвания; Баутс, Квирейн В.; тен Бринк, Алекс П.; Бучин, Кевин (2015), «Вычисление жадного гаечного ключа в линейном пространстве», Algorithmica , 73 (3): 589–606, arXiv : 1306.4919 , doi : 10.1007/s00453-015-0001-2 , MR 3411749 , S2CID 253977471
^ Jump up to: ^а ^б ^с Дас, Гаутама ; Нарасимхан, Гири (1997), «Быстрый алгоритм построения разреженных евклидовых ключей», Международный журнал вычислительной геометрии и приложений , 7 (4): 297–315, doi : 10.1142/S0218195997000193 , MR 1460840
^ Гудмундссон, Иоахим; Левкопулос, Христос; Нарасимхан, Гири (2002), «Быстрые жадные алгоритмы для построения разреженных геометрических ключей», SIAM Journal on Computing , 31 (5): 1479–1500, doi : 10.1137/S0097539700382947 , MR 1936655
^ Jump up to: ^а ^б Чандра, Барун; Дас, Гаутама ; Нарасимхан, Гири; Соарес, Хосе (1995), «Новые результаты о разреженности графов», Международный журнал вычислительной геометрии и приложений , 5 (1–2): 125–144, doi : 10.1142/S0218195995000088 , MR 1331179
^ Jump up to: ^а ^б Дас, Гаутама ; Хеффернан, Пол; Нарасимхан, Гири (1993), «Оптимально редкие гаечные ключи в трехмерном евклидовом пространстве», Труды девятого ежегодного симпозиума по вычислительной геометрии (SoCG '93) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 53–62, doi : 10.1145/160985.160998
^ Хар-Пелед, Сариэль ; Мендель, Мэнор (2006), «Быстрое построение сетей в низкоразмерных метриках и их приложения», SIAM Journal on Computing , 35 (5): 1148–1184, doi : 10.1137/S0097539704446281 , MR 2217141 , S2CID 37346335
^ Смид, Мишель Х.М. (2009), «Свойство слабой щели в метрических пространствах ограниченной удвоенной размерности», в Альберсе, Сюзанна ; Альт, Хельмут ; Нэхер, Стефан (ред.), «Эффективные алгоритмы: очерки, посвященные Курту Мельхорну по случаю его 60-летия» , Конспект лекций по информатике, том. 5760, Springer, стр. 275–289, номер документа : 10.1007/978-3-642-03456-5_19.

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

[ad2j-2] Альтёфер, Инго ; Дас, Гаутама ; Добкин, Дэвид ; Джозеф, Дебора (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-3] Jump up to: ^а ^б ^с Альтёфер, Инго ; Дас, Гаутама ; Добкин, Дэвид ; Джозеф, Дебора ; Соарес, Хосе (1993), «О редких ключах взвешенных графов», Discrete & Computational Geometry , 9 (1): 81–100, doi : 10.1007/BF02189308 , MR 1184695

[fs-4] Jump up to: ^а ^б ^с ^д ^и ^ж Фильцер, Арнольд; Соломон, Шей (2016), «Жадный гаечный ключ экзистенциально оптимален», Труды симпозиума ACM 2016 года по принципам распределенных вычислений (PODC '16) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 9–17, arXiv : 1605.06852 , дои : 10.1145/2933057.2933114 , S2CID 7229289

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

[ab3-6] Алевейнсе, Сандер, Пенсильвания; Баутс, Квирейн В.; тен Бринк, Алекс П.; Бучин, Кевин (2015), «Вычисление жадного гаечного ключа в линейном пространстве», Algorithmica , 73 (3): 589–606, arXiv : 1306.4919 , doi : 10.1007/s00453-015-0001-2 , MR 3411749 , S2CID 253977471

[dn-7] Jump up to: ^а ^б ^с Дас, Гаутама ; Нарасимхан, Гири (1997), «Быстрый алгоритм построения разреженных евклидовых ключей», Международный журнал вычислительной геометрии и приложений , 7 (4): 297–315, doi : 10.1142/S0218195997000193 , MR 1460840

[gln-8] Гудмундссон, Иоахим; Левкопулос, Христос; Нарасимхан, Гири (2002), «Быстрые жадные алгоритмы для построения разреженных геометрических ключей», SIAM Journal on Computing , 31 (5): 1479–1500, doi : 10.1137/S0097539700382947 , MR 1936655

[cdns-9] Jump up to: ^а ^б Чандра, Барун; Дас, Гаутама ; Нарасимхан, Гири; Соарес, Хосе (1995), «Новые результаты о разреженности графов», Международный журнал вычислительной геометрии и приложений , 5 (1–2): 125–144, doi : 10.1142/S0218195995000088 , MR 1331179

[dhn-10] Jump up to: ^а ^б Дас, Гаутама ; Хеффернан, Пол; Нарасимхан, Гири (1993), «Оптимально редкие гаечные ключи в трехмерном евклидовом пространстве», Труды девятого ежегодного симпозиума по вычислительной геометрии (SoCG '93) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 53–62, doi : 10.1145/160985.160998

[hm-11] Хар-Пелед, Сариэль ; Мендель, Мэнор (2006), «Быстрое построение сетей в низкоразмерных метриках и их приложения», SIAM Journal on Computing , 35 (5): 1148–1184, doi : 10.1137/S0097539704446281 , MR 2217141 , S2CID 37346335

[s-12] Смид, Мишель Х.М. (2009), «Свойство слабой щели в метрических пространствах ограниченной удвоенной размерности», в Альберсе, Сюзанна ; Альт, Хельмут ; Нэхер, Стефан (ред.), «Эффективные алгоритмы: очерки, посвященные Курту Мельхорну по случаю его 60-летия» , Конспект лекций по информатике, том. 5760, Springer, стр. 275–289, номер документа : 10.1007/978-3-642-03456-5_19.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]