Геометрические остовы: различия между версиями
Irina (обсуждение | вклад) (Новая страница: «Ключевые слова и синонимы Протяженность; t-остовы Постановка задачи Рассмотрим множест…») |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
Ключевые слова и синонимы | == Ключевые слова и синонимы == | ||
Протяженность; t-остовы | Протяженность; t-остовы | ||
Постановка задачи | == Постановка задачи == | ||
Рассмотрим множество S из n точек в d-мерном Евклидовом пространстве. Сеть на множестве S может быть смоделирована при помощи неориентированного графа G с множеством вершин S размера n и множеством ребер E, в котором каждое ребро (U, V) имеет вес. Геометрическая (евклидова) сеть представляет собой сеть, в которой весом ребра (u, v) является евклидово расстояние |uv| между его конечными точками. Пусть дано вещественное число t > 1. Мы говорим, что граф G является t-остовом множества S, если для каждой пары точек u, v 2 S существует путь в G с весом, не более чем в t раз превышающим евклидово расстояние между u и v. Минимальное значение t, при котором граф G является t-остовом S, называется коэффициентом растяжения, или протяженностью, G. Более детальное изложение процедуры построения t-остовов можно найти в книге Нарасимхана и Смида [ ]. В данной статье рассматривается построение t-остовов для заданного множества S из n точек в пространстве Rd и положительного вещественного числа t > 1, где d является константой. | Рассмотрим множество S из n точек в d-мерном Евклидовом пространстве. Сеть на множестве S может быть смоделирована при помощи неориентированного графа G с множеством вершин S размера n и множеством ребер E, в котором каждое ребро (U, V) имеет вес. Геометрическая (евклидова) сеть представляет собой сеть, в которой весом ребра (u, v) является евклидово расстояние |uv| между его конечными точками. Пусть дано вещественное число t > 1. Мы говорим, что граф G является t-остовом множества S, если для каждой пары точек u, v 2 S существует путь в G с весом, не более чем в t раз превышающим евклидово расстояние между u и v. Минимальное значение t, при котором граф G является t-остовом S, называется коэффициентом растяжения, или протяженностью, G. Более детальное изложение процедуры построения t-остовов можно найти в книге Нарасимхана и Смида [ ]. В данной статье рассматривается построение t-остовов для заданного множества S из n точек в пространстве Rd и положительного вещественного числа t > 1, где d является константой. | ||
Задача заключается в построении хорошего t-остова для S относительно следующих мер качества: | Задача заключается в построении хорошего t-остова для S относительно следующих мер качества: | ||
размер: количество ребер в графе. | размер: количество ребер в графе. | ||
степень: максимальное количество ребер, инцидентных вершине. | степень: максимальное количество ребер, инцидентных вершине. | ||
вес: сумма весов ребер. | вес: сумма весов ребер. | ||
диаметр остова: наименьшее целое число k, такое, что для любой пары вершин u и v из S существует путь в графе между u и v, длиной не более t • \uv\ и содержащий не более k ребер. | диаметр остова: наименьшее целое число k, такое, что для любой пары вершин u и v из S существует путь в графе между u и v, длиной не более t • \uv\ и содержащий не более k ребер. | ||
отказоустойчивость: сохранение работоспособности графа при отказе ребра, вершины или области. | отказоустойчивость: сохранение работоспособности графа при отказе ребра, вершины или области. | ||
Основные результаты | Таким образом, качественные t-остовы должны иметь высокое значение отказоустойчивости и малые размер, степень, вес и диаметр остова. | ||
== Основные результаты == | |||
Далее будут изложены три самых распространенных подхода к построению t-остова на множестве точек в евклидовом пространстве, а также приведено описание процесса построения отказоустойчивых остовов и остовов между многоугольными препятствиями; и, наконец, будут вкратце описаны динамические и кинетические остовы. | Далее будут изложены три самых распространенных подхода к построению t-остова на множестве точек в евклидовом пространстве, а также приведено описание процесса построения отказоустойчивых остовов и остовов между многоугольными препятствиями; и, наконец, будут вкратце описаны динамические и кинетические остовы. | ||
Остовы на точках в евклидовом пространстве | Остовы на точках в евклидовом пространстве | ||
Максимально изученными классами t-остовных сетей для точек в евклидовом пространстве являются ©-графы, WSPD-графы и жадные остовы. В следующих разделах будут изложены базовые идеи, лежащие в основе каждого из этих классов, а также приведены известные границы мер качества. | Максимально изученными классами t-остовных сетей для точек в евклидовом пространстве являются ©-графы, WSPD-графы и жадные остовы. В следующих разделах будут изложены базовые идеи, лежащие в основе каждого из этих классов, а также приведены известные границы мер качества. | ||
©-граф | ©-граф | ||
©-графы были независимо разработаны в конце 80-х Кларксоном и Кейлом. Основная идея заключалась в независимой обработке каждой точки p 2 S следующим образом. Разобьем Rd на k симплициальных конусов с угловым диаметром не более 9 и вершиной в точке p, где k = O(l/9d~1). К каждому непустому конусу C добавляется ребро, связывающее p и точку в C, ортогональная проекция которой на некоторый фиксированный луч в C, исходящий из p, является максимально близкой к p (см. рис. 1a). Полученный граф называется ©-графом на S. | ©-графы были независимо разработаны в конце 80-х Кларксоном и Кейлом. Основная идея заключалась в независимой обработке каждой точки p 2 S следующим образом. Разобьем Rd на k симплициальных конусов с угловым диаметром не более 9 и вершиной в точке p, где k = O(l/9d~1). К каждому непустому конусу C добавляется ребро, связывающее p и точку в C, ортогональная проекция которой на некоторый фиксированный луч в C, исходящий из p, является максимально близкой к p (см. рис. 1a). Полученный граф называется ©-графом на S. | ||
Теорема 1. ©-граф представляет собой t-остов на множестве S для t = 1/ (cos 9 — sin 9), имеющий O{nl9d~l) ребер, и может быть вычислен за время O((n/9d-1)logd~1 n) с использованием O(n/9d-1 + nlogd~2 n) памяти. | Теорема 1. ©-граф представляет собой t-остов на множестве S для t = 1/ (cos 9 — sin 9), имеющий O{nl9d~l) ребер, и может быть вычислен за время O((n/9d-1)logd~1 n) с использованием O(n/9d-1 + nlogd~2 n) памяти. | ||
Следующие варианты ©-графов задают границы на степень, диаметр и вес. | Следующие варианты ©-графов задают границы на степень, диаметр и вес. | ||
Геометрические остовы, рис. 1 | Геометрические остовы, рис. 1 | ||
a: ©-граф. b: граф с нерабочей областью | a: ©-граф. b: граф с нерабочей областью | ||
Остовы на базе списков с пропусками | Остовы на базе списков с пропусками | ||
Задача заключается в обобщении понятия списков с пропусками и применения их к построению остовов. Построим последовательность из h подмножеств, S1, S2, ... Sh, где S1 = S, а Si строится из Si-1 следующим образом (напоминающим уровни в списке пропусков). Для каждой точки в S-1 подбросим симметричную монету. Множество Si включает все точки S-1, для которых монета упала лицевой стороной вверх. Процесс построения заканчивается, когда Si = ;. Для каждого подмножества строится ©-граф. Объединение графов представляет собой остов S на базе списков с пропусками, имеющий протяженность t, O(n/9d~1) ребер и диаметр O(log n) с высокой вероятностью [3]. | Задача заключается в обобщении понятия списков с пропусками и применения их к построению остовов. Построим последовательность из h подмножеств, S1, S2, ... Sh, где S1 = S, а Si строится из Si-1 следующим образом (напоминающим уровни в списке пропусков). Для каждой точки в S-1 подбросим симметричную монету. Множество Si включает все точки S-1, для которых монета упала лицевой стороной вверх. Процесс построения заканчивается, когда Si = ;. Для каждого подмножества строится ©-граф. Объединение графов представляет собой остов S на базе списков с пропусками, имеющий протяженность t, O(n/9d~1) ребер и диаметр O(log n) с высокой вероятностью [3]. | ||
Жадный подход с пробелами | Жадный подход с пробелами | ||
Множество ориентированных ребер удовлетворяет свойству пробелов, если источники любых двух разных ребер разделены расстоянием, по крайней мере в несколько раз превышающим длины кратчайшего из двух ребер. Арья и Смид [5] предложили алгоритм, использующий свойство пробелов для определения того, может ли некоторое ребро быть добавлено к t-остовному графу. Используя свойство пробелов, можно доказать, что построенный остов имеет степень O{ll9d~l) и вес O(log n • wt(MST(S))), где wt(MST(S)) – вес минимального остовного дерева S. | Множество ориентированных ребер удовлетворяет свойству пробелов, если источники любых двух разных ребер разделены расстоянием, по крайней мере в несколько раз превышающим длины кратчайшего из двух ребер. Арья и Смид [5] предложили алгоритм, использующий свойство пробелов для определения того, может ли некоторое ребро быть добавлено к t-остовному графу. Используя свойство пробелов, можно доказать, что построенный остов имеет степень O{ll9d~l) и вес O(log n • wt(MST(S))), где wt(MST(S)) – вес минимального остовного дерева S. | ||
WSPD-граф | WSPD-граф | ||
Пусть A и B – два конечных множества точек в Rd. Будем называть A и B значительно удаленными по отношению к вещественному числу s > 0, если существуют два непересекающихся шара CA и CB одного и того же радиуса, такие, что CA содержит A, CB содержит B, а расстояние между CA и CB по меньшей мере в s раз превышает радиус CA. Значение s называется коэффициентом удаления. | Пусть A и B – два конечных множества точек в Rd. Будем называть A и B значительно удаленными по отношению к вещественному числу s > 0, если существуют два непересекающихся шара CA и CB одного и того же радиуса, такие, что CA содержит A, CB содержит B, а расстояние между CA и CB по меньшей мере в s раз превышает радиус CA. Значение s называется коэффициентом удаления. | ||
Определение 1. Пусть S – множество точек в пространстве Rd, а s > 0 – вещественное число. Декомпозицией значительно удаленных пар (well-separated pair decomposition, WSPD) для S относительно s является последовательность fAi ; Bi g, 1 < i < m, пар непустых подмножеств S, таких, что (1) Ai \ B i = ; для всех i = 1, 2, ... , m; (2) для каждой неориентированной пары {p, q} различных точек S существует ровно одна пара {Ai, Bi} в последовательности, такая, что p 2 Ai и q 2 Bi либо p 2 Bi и q 2 Ai; (3) Ai и Bi являются значительно удаленными относительно s для всех i = 1, 2, ... , m. | Определение 1. Пусть S – множество точек в пространстве Rd, а s > 0 – вещественное число. Декомпозицией значительно удаленных пар (well-separated pair decomposition, WSPD) для S относительно s является последовательность fAi ; Bi g, 1 < i < m, пар непустых подмножеств S, таких, что (1) Ai \ B i = ; для всех i = 1, 2, ... , m; (2) для каждой неориентированной пары {p, q} различных точек S существует ровно одна пара {Ai, Bi} в последовательности, такая, что p 2 Ai и q 2 Bi либо p 2 Bi и q 2 Ai; (3) Ai и Bi являются значительно удаленными относительно s для всех i = 1, 2, ... , m. | ||
Декомпозицию значительно удаленных пар разработали Кэллахан и Косарайю [ ]. Построение t-остова при помощи этого подхода заключается в построении декомпозиции S относительно коэффициента удаления s = (4(t + 1))/(t — 1). Вначале возьмем за остовный граф G = (S; ;) и будем итеративно добавлять ребра следующим образом. Для каждой значительно удаленной пары {A, B} из декомпозиции к графу добавляется ребро (a, b), где a и b – произвольные точки из A и B, соответственно. Полученный граф называется WSPD-графом на S. | Декомпозицию значительно удаленных пар разработали Кэллахан и Косарайю [ ]. Построение t-остова при помощи этого подхода заключается в построении декомпозиции S относительно коэффициента удаления s = (4(t + 1))/(t — 1). Вначале возьмем за остовный граф G = (S; ;) и будем итеративно добавлять ребра следующим образом. Для каждой значительно удаленной пары {A, B} из декомпозиции к графу добавляется ребро (a, b), где a и b – произвольные точки из A и B, соответственно. Полученный граф называется WSPD-графом на S. | ||
Теорема 2. WSPD-граф представляет собой t-остов на множестве S, имеющий O{nl9d~l) ребер, и может быть построен за время O(sdn + и log n), где s = 4(t + 1)/(t — 1). | Теорема 2. WSPD-граф представляет собой t-остов на множестве S, имеющий O{nl9d~l) ребер, и может быть построен за время O(sdn + и log n), где s = 4(t + 1)/(t — 1). | ||
В алгоритм можно внести модификации для получения графа с ограниченным диаметром или ограниченной степенью. | В алгоритм можно внести модификации для получения графа с ограниченным диаметром или ограниченной степенью. | ||
Ограниченный диаметр | Ограниченный диаметр | ||
Арья, Маунт и Смид [3] предложили модификацию алгоритма построения, в результате которой диаметр графа оказывается ограничен 2 log n. Вместо выбора произвольной точки в каждом значительно удаленном множестве их алгоритм тщательно выбирает особую точку для каждого множества. | Арья, Маунт и Смид [3] предложили модификацию алгоритма построения, в результате которой диаметр графа оказывается ограничен 2 log n. Вместо выбора произвольной точки в каждом значительно удаленном множестве их алгоритм тщательно выбирает особую точку для каждого множества. | ||
Ограниченная степень | Ограниченная степень | ||
Одна и та же точка v может быть частью нескольких значительно удаленных пар, и каждая из этих пар может сгенерировать ребро с конечной точкой в v. Арья и др. [ ] предложили алгоритм, сохраняющий только самое короткое ребро для каждого направления конуса, объединив таким образом подход к построению ©-графа с подходом для WSPD-графа. Добавив шаг постобработки, рассматривающий все вершины с высокой степенью, можно получить t-остов степени O(ll{t-l)2d-1). | Одна и та же точка v может быть частью нескольких значительно удаленных пар, и каждая из этих пар может сгенерировать ребро с конечной точкой в v. Арья и др. [ ] предложили алгоритм, сохраняющий только самое короткое ребро для каждого направления конуса, объединив таким образом подход к построению ©-графа с подходом для WSPD-графа. Добавив шаг постобработки, рассматривающий все вершины с высокой степенью, можно получить t-остов степени O(ll{t-l)2d-1). | ||
Жадный остов | Жадный остов | ||
Жадный алгоритм был впервые представлен в 1989 году Берном (см. также работу Ленкопулоса и Лингаса [15]) и с тех пор широко исследовался. Граф, построенный при помощи жадного алгоритма, будем называть жадным остовом. Основная идея заключается в итеративном построении графа G. Ребра полного графа обрабатываются в порядке возрастания длины. Проверка ребра (u, v) включает запрос о кратчайшем пути в частичном остовном графе G. Если кратчайший путь в G между u и v не превышает t • \uv, то ребро (u, v) отбрасывается, в противном случае оно добавляется к частичному остовному графу G. | Жадный алгоритм был впервые представлен в 1989 году Берном (см. также работу Ленкопулоса и Лингаса [15]) и с тех пор широко исследовался. Граф, построенный при помощи жадного алгоритма, будем называть жадным остовом. Основная идея заключается в итеративном построении графа G. Ребра полного графа обрабатываются в порядке возрастания длины. Проверка ребра (u, v) включает запрос о кратчайшем пути в частичном остовном графе G. Если кратчайший путь в G между u и v не превышает t • \uv, то ребро (u, v) отбрасывается, в противном случае оно добавляется к частичному остовному графу G. | ||
Дас, Нарасимхан и Салоу [ ] доказали, что жадный остов удовлетворяет так называемому «свойству прыжков». Множество неориентированных ребер E удовлетворяет свойству t-прыжков, если для любого k > 2 и любой возможной последовательности f(p1; q1)..: ; (pk; qk)g попарно различающихся ребер E, | Дас, Нарасимхан и Салоу [ ] доказали, что жадный остов удовлетворяет так называемому «свойству прыжков». Множество неориентированных ребер E удовлетворяет свойству t-прыжков, если для любого k > 2 и любой возможной последовательности f(p1; q1)..: ; (pk; qk)g попарно различающихся ребер E, | ||
Используя свойство прыжков, можно ограничить вес графа. Дас и Нарасимхан [ ] заметили, что жадный остов можно вычислить приближенно при удовлетворении свойства прыжков. Это наблюдение позволило разработать более быстрые алгоритмы для его построения. | Используя свойство прыжков, можно ограничить вес графа. Дас и Нарасимхан [ ] заметили, что жадный остов можно вычислить приближенно при удовлетворении свойства прыжков. Это наблюдение позволило разработать более быстрые алгоритмы для его построения. | ||
Теорема 3 ([14]). Приближенный жадный t-остов на множестве S, имеющий максимальную степень O(1/(t — l)2d~l) и вес O((1/(t - \)и~1 . wt(MST(S)))), может быть построен за время O(n/((t - 1)2d)log n). | Теорема 3 ([14]). Приближенный жадный t-остов на множестве S, имеющий максимальную степень O(1/(t — l)2d~l) и вес O((1/(t - \)и~1 . wt(MST(S)))), может быть построен за время O(n/((t - 1)2d)log n). | ||
Отказоустойчивые остовы | Отказоустойчивые остовы | ||
Понятие отказоустойчивых остовов было введено Левкопулосом и др. [ ] в 1998 году. Оно означает, что при отказе одной или нескольких вершин либо одного или нескольких ребер остов должен сохранить свои основные свойства. В частности, в том, что осталось от остова после отказа вершин или ребер, по-прежнему должен сохраниться короткий путь между любыми двумя вершинами. Шумай и Чжао [ ] показали, что жадный подход позволяет получить k-вершинный (или k-реберный) отказоустойчивый геометрический t-остов степени O(k) с общим весом O(k2 ■ wt(MST(S))); эти границы являются асимптотически оптимальными. | Понятие отказоустойчивых остовов было введено Левкопулосом и др. [ ] в 1998 году. Оно означает, что при отказе одной или нескольких вершин либо одного или нескольких ребер остов должен сохранить свои основные свойства. В частности, в том, что осталось от остова после отказа вершин или ребер, по-прежнему должен сохраниться короткий путь между любыми двумя вершинами. Шумай и Чжао [ ] показали, что жадный подход позволяет получить k-вершинный (или k-реберный) отказоустойчивый геометрический t-остов степени O(k) с общим весом O(k2 ■ wt(MST(S))); эти границы являются асимптотически оптимальными. | ||
Для геометрических остовов естественно рассматривать отказы областей – то есть отказы, уничтожающие все вершины и ребра, пересекающие некоторую нерабочую геометрическую область. Пусть для нерабочей области F граф G G F представляет собой часть G, оставшуюся после того, как точки из S, находящиеся внутри области F, и все ребра, пересекающие F, были удалены из графа; см. рис. 1b. Абам и др. [1] показали, как строить t-остовы размера O(nlogn), являющиеся отказоустойчивыми при отказе любой выпуклой области. Если разрешается использовать точки Штейнера, можно получить t-остов линейного размера. | Для геометрических остовов естественно рассматривать отказы областей – то есть отказы, уничтожающие все вершины и ребра, пересекающие некоторую нерабочую геометрическую область. Пусть для нерабочей области F граф G G F представляет собой часть G, оставшуюся после того, как точки из S, находящиеся внутри области F, и все ребра, пересекающие F, были удалены из графа; см. рис. 1b. Абам и др. [1] показали, как строить t-остовы размера O(nlogn), являющиеся отказоустойчивыми при отказе любой выпуклой области. Если разрешается использовать точки Штейнера, можно получить t-остов линейного размера. | ||
Остовы с многоугольными препятствиями | Остовы с многоугольными препятствиями | ||
Граф видимости на множестве попарно непересекающихся многоугольников называется графом взаимовидимых областей. Каждая многоугольная вершина является вершиной в графе, а каждое ребро представляет видимую связь между ними: если две вершины видят друг друга, между ними строится ребро. Этот граф полезен благодаря тому, что содержит кратчайший путь, огибающий препятствия, между парой любых вершин. | Граф видимости на множестве попарно непересекающихся многоугольников называется графом взаимовидимых областей. Каждая многоугольная вершина является вершиной в графе, а каждое ребро представляет видимую связь между ними: если две вершины видят друг друга, между ними строится ребро. Этот граф полезен благодаря тому, что содержит кратчайший путь, огибающий препятствия, между парой любых вершин. | ||
Дас [9] показал, что t-остов графа видимости для множества точек на евклидовой плоскости можно построить при помощи алгоритма построения ©-графа с последующим этапом усечения. Полученный граф будет иметь линейный размер и константную степень. | Дас [9] показал, что t-остов графа видимости для множества точек на евклидовой плоскости можно построить при помощи алгоритма построения ©-графа с последующим этапом усечения. Полученный граф будет иметь линейный размер и константную степень. | ||
Динамические и кинетические остовы | Динамические и кинетические остовы | ||
О динамических или кинетических остовах известно не так уж много. Арья и др. [ ] предложили структуру данных размера O(n log n), поддерживающую остов на базе списков с пропусками, описанный выше, с ожидаемым амортизированным временем вставки и удаления O(log и log log n) на основе модели случайных обновлений. | О динамических или кинетических остовах известно не так уж много. Арья и др. [ ] предложили структуру данных размера O(n log n), поддерживающую остов на базе списков с пропусками, описанный выше, с ожидаемым амортизированным временем вставки и удаления O(log и log log n) на основе модели случайных обновлений. | ||
Гао и др. [13] показали, как поддерживать t-остов размера O(n/(t-l)d) с максимальной степенью O(l/(f-2)d logo;) и временем вставки и удаления O((loga)/(f — 1)d), где a обозначает пропорциональность S, т.е. отношение максимального расстояния между парой вершин к минимальному. Алгоритм основан на использовании иерархической структуры T с O(log a) уровнями, каждый уровень которой содержит множество центров (подмножество S). Каждая вершина v на уровне i в структуре T связана ребрами со всеми остальными вершинами уровня i, находящимися на расстоянии не более O(2i/(t — 1)) от v. Полученный граф является t-остовом S и может поддерживаться вышеописанным образом. Этот подход может быть обобщен до кинетического случая таким образом, чтобы количество событий в процессе поддержки остова составляло O(n2 log n) при псевдоалгебраическом характере перемещения. Каждое событие может быть обновлено за время O((loga)/(f - 1)d). | Гао и др. [13] показали, как поддерживать t-остов размера O(n/(t-l)d) с максимальной степенью O(l/(f-2)d logo;) и временем вставки и удаления O((loga)/(f — 1)d), где a обозначает пропорциональность S, т.е. отношение максимального расстояния между парой вершин к минимальному. Алгоритм основан на использовании иерархической структуры T с O(log a) уровнями, каждый уровень которой содержит множество центров (подмножество S). Каждая вершина v на уровне i в структуре T связана ребрами со всеми остальными вершинами уровня i, находящимися на расстоянии не более O(2i/(t — 1)) от v. Полученный граф является t-остовом S и может поддерживаться вышеописанным образом. Этот подход может быть обобщен до кинетического случая таким образом, чтобы количество событий в процессе поддержки остова составляло O(n2 log n) при псевдоалгебраическом характере перемещения. Каждое событие может быть обновлено за время O((loga)/(f - 1)d). | ||
Применение | == Применение == | ||
Алгоритмы построения разреженных остовов получили широкое применение в таких областях, как поиск в метрическом пространстве [1], который включает запрос по содержанию в мультимедийных объектах, текстовый информационный поиск, распознавание образов и аппроксимацию функций. Еще одним примером является широковещательная рассылка в сетях коммуникаций [ ]. Несколько хорошо известных теоретических работ также основываются на построении t-остовов – к примеру, Рао и Смит [19] совершили прорыв, предложив схему аппроксимации с оптимальным временем O(nlog n) для хорошо известной евклидовой задачи коммивояжера с использованием t-остовов (или баньянов). А Шумай и Лингас [ ] предложили схемы аппроксимации для задач о многосвязности с нахождением объектов минимальной стоимости в геометрических сетях. | Алгоритмы построения разреженных остовов получили широкое применение в таких областях, как поиск в метрическом пространстве [1], который включает запрос по содержанию в мультимедийных объектах, текстовый информационный поиск, распознавание образов и аппроксимацию функций. Еще одним примером является широковещательная рассылка в сетях коммуникаций [ ]. Несколько хорошо известных теоретических работ также основываются на построении t-остовов – к примеру, Рао и Смит [19] совершили прорыв, предложив схему аппроксимации с оптимальным временем O(nlog n) для хорошо известной евклидовой задачи коммивояжера с использованием t-остовов (или баньянов). А Шумай и Лингас [ ] предложили схемы аппроксимации для задач о многосвязности с нахождением объектов минимальной стоимости в геометрических сетях. | ||
Открытые вопросы | == Открытые вопросы == | ||
В этой сфере остается много нерешенных задач. Стоит упомянуть некоторые из них: | В этой сфере остается много нерешенных задач. Стоит упомянуть некоторые из них: | ||
1. Разработка алгоритма построения динамического t-остова, который можно обновлять за время O(logc n) для некоторого константного значения c. | 1. Разработка алгоритма построения динамического t-остова, который можно обновлять за время O(logc n) для некоторого константного значения c. | ||
2. Определение, существует ли отказоустойчивый t-остов линейного размера для ситуации отказов выпуклых областей. | 2. Определение, существует ли отказоустойчивый t-остов линейного размера для ситуации отказов выпуклых областей. | ||
3. Алгоритм построения k-вершинного отказоустойчивого остова, который предложили Шумай и Чжао [8], позволяет получить k-вершинный отказоустойчивый t-остов степени O(k) с общим весом O(k2 ■ wt(MST(S))). Однако до сих пор неизвестны способы его эффективной реализации. Можно ли вычислить такой остов за время O(nlog n + kn)? | 3. Алгоритм построения k-вершинного отказоустойчивого остова, который предложили Шумай и Чжао [8], позволяет получить k-вершинный отказоустойчивый t-остов степени O(k) с общим весом O(k2 ■ wt(MST(S))). Однако до сих пор неизвестны способы его эффективной реализации. Можно ли вычислить такой остов за время O(nlog n + kn)? | ||
4. Ограничение веса остовов на базе списков с пропусками. | 4. Ограничение веса остовов на базе списков с пропусками. | ||
Экспериментальные результаты | == Экспериментальные результаты == | ||
Задача построения остовов активно исследовалась с теоретической точки зрения, но получила гораздо меньше внимания с практической, или экспериментальной, стороны. Наварро и Паредес [ ] предложили четыре эвристики для множеств точек в пространстве высоких размерностей (d = 20) и эмпирическими методами показали, что время выполнения составило O(n2.24), а количество ребер в полученных графах – O(n1.13). Недавно Фарши и Гудмундссон [12] провели тщательное сравнение алгоритмов построения остовов, упоминавшихся в разделе «Остовы на точках в евклидовом пространстве». | Задача построения остовов активно исследовалась с теоретической точки зрения, но получила гораздо меньше внимания с практической, или экспериментальной, стороны. Наварро и Паредес [ ] предложили четыре эвристики для множеств точек в пространстве высоких размерностей (d = 20) и эмпирическими методами показали, что время выполнения составило O(n2.24), а количество ребер в полученных графах – O(n1.13). Недавно Фарши и Гудмундссон [12] провели тщательное сравнение алгоритмов построения остовов, упоминавшихся в разделе «Остовы на точках в евклидовом пространстве». | ||
См. также | == См. также == | ||
* [[Применение геометрических остовных сетей]] | |||
* [[Аппроксимация метрических пространств древесными метриками]] | |||
* [[Протяженность геометрических сетей]] | |||
* [[Планарные геометрические остовы]] | |||
* [[Алгоритм поиска кратчайших путей с единственным источником]] | |||
* [[Разреженные остовы графов]] | |||
* [[Декомпозиция значительно удаленных пар]] | |||
Литература | == Литература == | ||
1. Abam, M.A., de Berg, M., Farshi, M., Gudmundsson, J.: Region-fault tolerant geometric spanners. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 7-9 January 2007 | 1. Abam, M.A., de Berg, M., Farshi, M., Gudmundsson, J.: Region-fault tolerant geometric spanners. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 7-9 January 2007 | ||
2. Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.: Euclidean spanners: short, thin, and lanky. In: Proceedings of the 27th ACM Symposium on Theory of Computing, pp. 489-498. Las Vegas, 29 May-1 June 1995 | 2. Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.: Euclidean spanners: short, thin, and lanky. In: Proceedings of the 27th ACM Symposium on Theory of Computing, pp. 489-498. Las Vegas, 29 May-1 June 1995 | ||
3. Arya, S., Mount, D.M., Smid, M.: Randomized and deterministic algorithms for geometric spanners of small diameter. In: Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pp. 703-712. Santa Fe, 20-22 November 1994 | 3. Arya, S., Mount, D.M., Smid, M.: Randomized and deterministic algorithms for geometric spanners of small diameter. In: Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pp. 703-712. Santa Fe, 20-22 November 1994 | ||
4. Arya, S., Mount, D.M., Smid, M.: Dynamic algorithms for geometric spanners of small diameter: Randomized solutions. Comput. Geom. Theor. Appl. 13(2), 91 -107 (1999) | 4. Arya, S., Mount, D.M., Smid, M.: Dynamic algorithms for geometric spanners of small diameter: Randomized solutions. Comput. Geom. Theor. Appl. 13(2), 91 -107 (1999) | ||
5. Arya, S., Smid, M.: Efficient construction of a bounded-degree spanner with low weight. Algorithmica 17, 33-54 (1997) | 5. Arya, S., Smid, M.: Efficient construction of a bounded-degree spanner with low weight. Algorithmica 17, 33-54 (1997) | ||
6. Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42,67-90 (1995) | 6. Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42,67-90 (1995) | ||
7. Czumaj, A., Lingas, A.: Fast approximation schemes for Euclidean multi-connectivity problems. In: Proceedings of the 27th International Colloquium on Automata, Languages and | 7. Czumaj, A., Lingas, A.: Fast approximation schemes for Euclidean multi-connectivity problems. In: Proceedings of the 27th International Colloquium on Automata, Languages and | ||
Programming. Lect. Notes Comput. Sci. 1853,856-868 (2000) | Programming. Lect. Notes Comput. Sci. 1853,856-868 (2000) | ||
8. Czumaj, A., Zhao, H.: Fault-tolerant geometric spanners. Discret. Comput. Geom. 32(2), 207-230 (2004) | 8. Czumaj, A., Zhao, H.: Fault-tolerant geometric spanners. Discret. Comput. Geom. 32(2), 207-230 (2004) | ||
9. Das, G.: The visibility graph contains a bounded-degree spanner. In: Proceedings of the 9th Canadian Conference on Computational Geometry, Kingston, 11-14 August 1997 | 9. Das, G.: The visibility graph contains a bounded-degree spanner. In: Proceedings of the 9th Canadian Conference on Computational Geometry, Kingston, 11-14 August 1997 | ||
10. Das, G., Narasimhan, G.: A fast algorithm for constructing sparse Euclidean spanners. Int. J. Comput. Geom. Appl. 7,297-315(1997) | 10. Das, G., Narasimhan, G.: A fast algorithm for constructing sparse Euclidean spanners. Int. J. Comput. Geom. Appl. 7,297-315(1997) | ||
11. Das, G., Narasimhan, G., Salowe, J.: A new way to weigh malnourished Euclidean graphs. In: Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, pp. 215-222. San Francisco, 22-24 January 1995 | 11. Das, G., Narasimhan, G., Salowe, J.: A new way to weigh malnourished Euclidean graphs. In: Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, pp. 215-222. San Francisco, 22-24 January 1995 | ||
12. Farshi, M., Gudmundsson, J.: Experimental study of geometric t-spanners. In: Proceedings of the 13th Annual European Symposium on Algorithms. Lect. Notes Comput. Sci. 3669, 556-567 (2005) | 12. Farshi, M., Gudmundsson, J.: Experimental study of geometric t-spanners. In: Proceedings of the 13th Annual European Symposium on Algorithms. Lect. Notes Comput. Sci. 3669, 556-567 (2005) | ||
13. Gao, J., Guibas, L.J., Nguyen, A.: Deformable spanners and applications. In: Proceedings of the 20th ACM Symposium on Computational Geometry, pp. 190-199, New York, 9-11 June 2004 | 13. Gao, J., Guibas, L.J., Nguyen, A.: Deformable spanners and applications. In: Proceedings of the 20th ACM Symposium on Computational Geometry, pp. 190-199, New York, 9-11 June 2004 | ||
14. Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Improved greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput. 31(5), 1479-1500 (2002) | 14. Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Improved greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput. 31(5), 1479-1500 (2002) | ||
15. Levcopoulos, C., Lingas, A.: There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees. Algorithmica 8(3), 251-256 (1992) | 15. Levcopoulos, C., Lingas, A.: There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees. Algorithmica 8(3), 251-256 (1992) | ||
16. Levcopoulos, C., Narasimhan, G., Smid, M.: Improved algorithms for constructing fault-tolerant spanners. Algorithmica 32, 144-156(2002) | 16. Levcopoulos, C., Narasimhan, G., Smid, M.: Improved algorithms for constructing fault-tolerant spanners. Algorithmica 32, 144-156(2002) | ||
17. Li, X.Y.: Applications of computational geometry in wireless ad hoc networks. In: Cheng, X.Z., Huang, X., Du, D.Z. (eds.) Ad Hoc Wireless Networking, pp. 197-264. Kluwer, Dordrecht (2003) | 17. Li, X.Y.: Applications of computational geometry in wireless ad hoc networks. In: Cheng, X.Z., Huang, X., Du, D.Z. (eds.) Ad Hoc Wireless Networking, pp. 197-264. Kluwer, Dordrecht (2003) | ||
18. Narasimhan, G., Smid, M.: Geometric spanner networks. Cambridge University Press, New York (2006) | 18. Narasimhan, G., Smid, M.: Geometric spanner networks. Cambridge University Press, New York (2006) | ||
19. Navarro, G., Paredes, R.: Practical construction of metric t-spanners. In: Proceedings of the 5th Workshop on Algorithm Engineering and Experiments, pp. 69-81, 11 January 2003. SIAM Press, Baltimore | 19. Navarro, G., Paredes, R.: Practical construction of metric t-spanners. In: Proceedings of the 5th Workshop on Algorithm Engineering and Experiments, pp. 69-81, 11 January 2003. SIAM Press, Baltimore | ||
20. Rao, S., Smith, W.D.: Approximating geometrical graphs via spanners and banyans. In: Proceedings of the 30th ACM Symposium on Theory of Computing, pp. 540-550. Dallas, 23-26 May 1998 | 20. Rao, S., Smith, W.D.: Approximating geometrical graphs via spanners and banyans. In: Proceedings of the 30th ACM Symposium on Theory of Computing, pp. 540-550. Dallas, 23-26 May 1998 | ||
Версия от 13:30, 29 января 2018
Ключевые слова и синонимы
Протяженность; t-остовы
Постановка задачи
Рассмотрим множество S из n точек в d-мерном Евклидовом пространстве. Сеть на множестве S может быть смоделирована при помощи неориентированного графа G с множеством вершин S размера n и множеством ребер E, в котором каждое ребро (U, V) имеет вес. Геометрическая (евклидова) сеть представляет собой сеть, в которой весом ребра (u, v) является евклидово расстояние |uv| между его конечными точками. Пусть дано вещественное число t > 1. Мы говорим, что граф G является t-остовом множества S, если для каждой пары точек u, v 2 S существует путь в G с весом, не более чем в t раз превышающим евклидово расстояние между u и v. Минимальное значение t, при котором граф G является t-остовом S, называется коэффициентом растяжения, или протяженностью, G. Более детальное изложение процедуры построения t-остовов можно найти в книге Нарасимхана и Смида [ ]. В данной статье рассматривается построение t-остовов для заданного множества S из n точек в пространстве Rd и положительного вещественного числа t > 1, где d является константой.
Задача заключается в построении хорошего t-остова для S относительно следующих мер качества:
размер: количество ребер в графе.
степень: максимальное количество ребер, инцидентных вершине.
вес: сумма весов ребер.
диаметр остова: наименьшее целое число k, такое, что для любой пары вершин u и v из S существует путь в графе между u и v, длиной не более t • \uv\ и содержащий не более k ребер.
отказоустойчивость: сохранение работоспособности графа при отказе ребра, вершины или области.
Таким образом, качественные t-остовы должны иметь высокое значение отказоустойчивости и малые размер, степень, вес и диаметр остова.
Основные результаты
Далее будут изложены три самых распространенных подхода к построению t-остова на множестве точек в евклидовом пространстве, а также приведено описание процесса построения отказоустойчивых остовов и остовов между многоугольными препятствиями; и, наконец, будут вкратце описаны динамические и кинетические остовы.
Остовы на точках в евклидовом пространстве
Максимально изученными классами t-остовных сетей для точек в евклидовом пространстве являются ©-графы, WSPD-графы и жадные остовы. В следующих разделах будут изложены базовые идеи, лежащие в основе каждого из этих классов, а также приведены известные границы мер качества.
©-граф
©-графы были независимо разработаны в конце 80-х Кларксоном и Кейлом. Основная идея заключалась в независимой обработке каждой точки p 2 S следующим образом. Разобьем Rd на k симплициальных конусов с угловым диаметром не более 9 и вершиной в точке p, где k = O(l/9d~1). К каждому непустому конусу C добавляется ребро, связывающее p и точку в C, ортогональная проекция которой на некоторый фиксированный луч в C, исходящий из p, является максимально близкой к p (см. рис. 1a). Полученный граф называется ©-графом на S.
Теорема 1. ©-граф представляет собой t-остов на множестве S для t = 1/ (cos 9 — sin 9), имеющий O{nl9d~l) ребер, и может быть вычислен за время O((n/9d-1)logd~1 n) с использованием O(n/9d-1 + nlogd~2 n) памяти.
Следующие варианты ©-графов задают границы на степень, диаметр и вес.
Геометрические остовы, рис. 1 a: ©-граф. b: граф с нерабочей областью
Остовы на базе списков с пропусками
Задача заключается в обобщении понятия списков с пропусками и применения их к построению остовов. Построим последовательность из h подмножеств, S1, S2, ... Sh, где S1 = S, а Si строится из Si-1 следующим образом (напоминающим уровни в списке пропусков). Для каждой точки в S-1 подбросим симметричную монету. Множество Si включает все точки S-1, для которых монета упала лицевой стороной вверх. Процесс построения заканчивается, когда Si = ;. Для каждого подмножества строится ©-граф. Объединение графов представляет собой остов S на базе списков с пропусками, имеющий протяженность t, O(n/9d~1) ребер и диаметр O(log n) с высокой вероятностью [3].
Жадный подход с пробелами
Множество ориентированных ребер удовлетворяет свойству пробелов, если источники любых двух разных ребер разделены расстоянием, по крайней мере в несколько раз превышающим длины кратчайшего из двух ребер. Арья и Смид [5] предложили алгоритм, использующий свойство пробелов для определения того, может ли некоторое ребро быть добавлено к t-остовному графу. Используя свойство пробелов, можно доказать, что построенный остов имеет степень O{ll9d~l) и вес O(log n • wt(MST(S))), где wt(MST(S)) – вес минимального остовного дерева S.
WSPD-граф
Пусть A и B – два конечных множества точек в Rd. Будем называть A и B значительно удаленными по отношению к вещественному числу s > 0, если существуют два непересекающихся шара CA и CB одного и того же радиуса, такие, что CA содержит A, CB содержит B, а расстояние между CA и CB по меньшей мере в s раз превышает радиус CA. Значение s называется коэффициентом удаления.
Определение 1. Пусть S – множество точек в пространстве Rd, а s > 0 – вещественное число. Декомпозицией значительно удаленных пар (well-separated pair decomposition, WSPD) для S относительно s является последовательность fAi ; Bi g, 1 < i < m, пар непустых подмножеств S, таких, что (1) Ai \ B i = ; для всех i = 1, 2, ... , m; (2) для каждой неориентированной пары {p, q} различных точек S существует ровно одна пара {Ai, Bi} в последовательности, такая, что p 2 Ai и q 2 Bi либо p 2 Bi и q 2 Ai; (3) Ai и Bi являются значительно удаленными относительно s для всех i = 1, 2, ... , m.
Декомпозицию значительно удаленных пар разработали Кэллахан и Косарайю [ ]. Построение t-остова при помощи этого подхода заключается в построении декомпозиции S относительно коэффициента удаления s = (4(t + 1))/(t — 1). Вначале возьмем за остовный граф G = (S; ;) и будем итеративно добавлять ребра следующим образом. Для каждой значительно удаленной пары {A, B} из декомпозиции к графу добавляется ребро (a, b), где a и b – произвольные точки из A и B, соответственно. Полученный граф называется WSPD-графом на S.
Теорема 2. WSPD-граф представляет собой t-остов на множестве S, имеющий O{nl9d~l) ребер, и может быть построен за время O(sdn + и log n), где s = 4(t + 1)/(t — 1).
В алгоритм можно внести модификации для получения графа с ограниченным диаметром или ограниченной степенью.
Ограниченный диаметр
Арья, Маунт и Смид [3] предложили модификацию алгоритма построения, в результате которой диаметр графа оказывается ограничен 2 log n. Вместо выбора произвольной точки в каждом значительно удаленном множестве их алгоритм тщательно выбирает особую точку для каждого множества.
Ограниченная степень
Одна и та же точка v может быть частью нескольких значительно удаленных пар, и каждая из этих пар может сгенерировать ребро с конечной точкой в v. Арья и др. [ ] предложили алгоритм, сохраняющий только самое короткое ребро для каждого направления конуса, объединив таким образом подход к построению ©-графа с подходом для WSPD-графа. Добавив шаг постобработки, рассматривающий все вершины с высокой степенью, можно получить t-остов степени O(ll{t-l)2d-1).
Жадный остов
Жадный алгоритм был впервые представлен в 1989 году Берном (см. также работу Ленкопулоса и Лингаса [15]) и с тех пор широко исследовался. Граф, построенный при помощи жадного алгоритма, будем называть жадным остовом. Основная идея заключается в итеративном построении графа G. Ребра полного графа обрабатываются в порядке возрастания длины. Проверка ребра (u, v) включает запрос о кратчайшем пути в частичном остовном графе G. Если кратчайший путь в G между u и v не превышает t • \uv, то ребро (u, v) отбрасывается, в противном случае оно добавляется к частичному остовному графу G.
Дас, Нарасимхан и Салоу [ ] доказали, что жадный остов удовлетворяет так называемому «свойству прыжков». Множество неориентированных ребер E удовлетворяет свойству t-прыжков, если для любого k > 2 и любой возможной последовательности f(p1; q1)..: ; (pk; qk)g попарно различающихся ребер E,
Используя свойство прыжков, можно ограничить вес графа. Дас и Нарасимхан [ ] заметили, что жадный остов можно вычислить приближенно при удовлетворении свойства прыжков. Это наблюдение позволило разработать более быстрые алгоритмы для его построения.
Теорема 3 ([14]). Приближенный жадный t-остов на множестве S, имеющий максимальную степень O(1/(t — l)2d~l) и вес O((1/(t - \)и~1 . wt(MST(S)))), может быть построен за время O(n/((t - 1)2d)log n).
Отказоустойчивые остовы
Понятие отказоустойчивых остовов было введено Левкопулосом и др. [ ] в 1998 году. Оно означает, что при отказе одной или нескольких вершин либо одного или нескольких ребер остов должен сохранить свои основные свойства. В частности, в том, что осталось от остова после отказа вершин или ребер, по-прежнему должен сохраниться короткий путь между любыми двумя вершинами. Шумай и Чжао [ ] показали, что жадный подход позволяет получить k-вершинный (или k-реберный) отказоустойчивый геометрический t-остов степени O(k) с общим весом O(k2 ■ wt(MST(S))); эти границы являются асимптотически оптимальными.
Для геометрических остовов естественно рассматривать отказы областей – то есть отказы, уничтожающие все вершины и ребра, пересекающие некоторую нерабочую геометрическую область. Пусть для нерабочей области F граф G G F представляет собой часть G, оставшуюся после того, как точки из S, находящиеся внутри области F, и все ребра, пересекающие F, были удалены из графа; см. рис. 1b. Абам и др. [1] показали, как строить t-остовы размера O(nlogn), являющиеся отказоустойчивыми при отказе любой выпуклой области. Если разрешается использовать точки Штейнера, можно получить t-остов линейного размера.
Остовы с многоугольными препятствиями
Граф видимости на множестве попарно непересекающихся многоугольников называется графом взаимовидимых областей. Каждая многоугольная вершина является вершиной в графе, а каждое ребро представляет видимую связь между ними: если две вершины видят друг друга, между ними строится ребро. Этот граф полезен благодаря тому, что содержит кратчайший путь, огибающий препятствия, между парой любых вершин.
Дас [9] показал, что t-остов графа видимости для множества точек на евклидовой плоскости можно построить при помощи алгоритма построения ©-графа с последующим этапом усечения. Полученный граф будет иметь линейный размер и константную степень.
Динамические и кинетические остовы
О динамических или кинетических остовах известно не так уж много. Арья и др. [ ] предложили структуру данных размера O(n log n), поддерживающую остов на базе списков с пропусками, описанный выше, с ожидаемым амортизированным временем вставки и удаления O(log и log log n) на основе модели случайных обновлений.
Гао и др. [13] показали, как поддерживать t-остов размера O(n/(t-l)d) с максимальной степенью O(l/(f-2)d logo;) и временем вставки и удаления O((loga)/(f — 1)d), где a обозначает пропорциональность S, т.е. отношение максимального расстояния между парой вершин к минимальному. Алгоритм основан на использовании иерархической структуры T с O(log a) уровнями, каждый уровень которой содержит множество центров (подмножество S). Каждая вершина v на уровне i в структуре T связана ребрами со всеми остальными вершинами уровня i, находящимися на расстоянии не более O(2i/(t — 1)) от v. Полученный граф является t-остовом S и может поддерживаться вышеописанным образом. Этот подход может быть обобщен до кинетического случая таким образом, чтобы количество событий в процессе поддержки остова составляло O(n2 log n) при псевдоалгебраическом характере перемещения. Каждое событие может быть обновлено за время O((loga)/(f - 1)d).
Применение
Алгоритмы построения разреженных остовов получили широкое применение в таких областях, как поиск в метрическом пространстве [1], который включает запрос по содержанию в мультимедийных объектах, текстовый информационный поиск, распознавание образов и аппроксимацию функций. Еще одним примером является широковещательная рассылка в сетях коммуникаций [ ]. Несколько хорошо известных теоретических работ также основываются на построении t-остовов – к примеру, Рао и Смит [19] совершили прорыв, предложив схему аппроксимации с оптимальным временем O(nlog n) для хорошо известной евклидовой задачи коммивояжера с использованием t-остовов (или баньянов). А Шумай и Лингас [ ] предложили схемы аппроксимации для задач о многосвязности с нахождением объектов минимальной стоимости в геометрических сетях.
Открытые вопросы
В этой сфере остается много нерешенных задач. Стоит упомянуть некоторые из них:
1. Разработка алгоритма построения динамического t-остова, который можно обновлять за время O(logc n) для некоторого константного значения c.
2. Определение, существует ли отказоустойчивый t-остов линейного размера для ситуации отказов выпуклых областей.
3. Алгоритм построения k-вершинного отказоустойчивого остова, который предложили Шумай и Чжао [8], позволяет получить k-вершинный отказоустойчивый t-остов степени O(k) с общим весом O(k2 ■ wt(MST(S))). Однако до сих пор неизвестны способы его эффективной реализации. Можно ли вычислить такой остов за время O(nlog n + kn)?
4. Ограничение веса остовов на базе списков с пропусками.
Экспериментальные результаты
Задача построения остовов активно исследовалась с теоретической точки зрения, но получила гораздо меньше внимания с практической, или экспериментальной, стороны. Наварро и Паредес [ ] предложили четыре эвристики для множеств точек в пространстве высоких размерностей (d = 20) и эмпирическими методами показали, что время выполнения составило O(n2.24), а количество ребер в полученных графах – O(n1.13). Недавно Фарши и Гудмундссон [12] провели тщательное сравнение алгоритмов построения остовов, упоминавшихся в разделе «Остовы на точках в евклидовом пространстве».
См. также
- Применение геометрических остовных сетей
- Аппроксимация метрических пространств древесными метриками
- Протяженность геометрических сетей
- Планарные геометрические остовы
- Алгоритм поиска кратчайших путей с единственным источником
- Разреженные остовы графов
- Декомпозиция значительно удаленных пар
Литература
1. Abam, M.A., de Berg, M., Farshi, M., Gudmundsson, J.: Region-fault tolerant geometric spanners. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 7-9 January 2007
2. Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.: Euclidean spanners: short, thin, and lanky. In: Proceedings of the 27th ACM Symposium on Theory of Computing, pp. 489-498. Las Vegas, 29 May-1 June 1995
3. Arya, S., Mount, D.M., Smid, M.: Randomized and deterministic algorithms for geometric spanners of small diameter. In: Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pp. 703-712. Santa Fe, 20-22 November 1994
4. Arya, S., Mount, D.M., Smid, M.: Dynamic algorithms for geometric spanners of small diameter: Randomized solutions. Comput. Geom. Theor. Appl. 13(2), 91 -107 (1999)
5. Arya, S., Smid, M.: Efficient construction of a bounded-degree spanner with low weight. Algorithmica 17, 33-54 (1997)
6. Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42,67-90 (1995)
7. Czumaj, A., Lingas, A.: Fast approximation schemes for Euclidean multi-connectivity problems. In: Proceedings of the 27th International Colloquium on Automata, Languages and Programming. Lect. Notes Comput. Sci. 1853,856-868 (2000)
8. Czumaj, A., Zhao, H.: Fault-tolerant geometric spanners. Discret. Comput. Geom. 32(2), 207-230 (2004)
9. Das, G.: The visibility graph contains a bounded-degree spanner. In: Proceedings of the 9th Canadian Conference on Computational Geometry, Kingston, 11-14 August 1997
10. Das, G., Narasimhan, G.: A fast algorithm for constructing sparse Euclidean spanners. Int. J. Comput. Geom. Appl. 7,297-315(1997)
11. Das, G., Narasimhan, G., Salowe, J.: A new way to weigh malnourished Euclidean graphs. In: Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, pp. 215-222. San Francisco, 22-24 January 1995
12. Farshi, M., Gudmundsson, J.: Experimental study of geometric t-spanners. In: Proceedings of the 13th Annual European Symposium on Algorithms. Lect. Notes Comput. Sci. 3669, 556-567 (2005)
13. Gao, J., Guibas, L.J., Nguyen, A.: Deformable spanners and applications. In: Proceedings of the 20th ACM Symposium on Computational Geometry, pp. 190-199, New York, 9-11 June 2004
14. Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Improved greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput. 31(5), 1479-1500 (2002)
15. Levcopoulos, C., Lingas, A.: There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees. Algorithmica 8(3), 251-256 (1992)
16. Levcopoulos, C., Narasimhan, G., Smid, M.: Improved algorithms for constructing fault-tolerant spanners. Algorithmica 32, 144-156(2002)
17. Li, X.Y.: Applications of computational geometry in wireless ad hoc networks. In: Cheng, X.Z., Huang, X., Du, D.Z. (eds.) Ad Hoc Wireless Networking, pp. 197-264. Kluwer, Dordrecht (2003)
18. Narasimhan, G., Smid, M.: Geometric spanner networks. Cambridge University Press, New York (2006)
19. Navarro, G., Paredes, R.: Practical construction of metric t-spanners. In: Proceedings of the 5th Workshop on Algorithm Engineering and Experiments, pp. 69-81, 11 January 2003. SIAM Press, Baltimore
20. Rao, S., Smith, W.D.: Approximating geometrical graphs via spanners and banyans. In: Proceedings of the 30th ACM Symposium on Theory of Computing, pp. 540-550. Dallas, 23-26 May 1998