4551
правка
Применение геометрических остовных сетей: различия между версиями
Перейти к навигации
Перейти к поиску
Применение геометрических остовных сетей (посмотреть исходный код)
Версия от 14:00, 13 октября 2016
, 13 октября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 24: | Строка 24: | ||
== Основные результаты == | == Основные результаты == | ||
Основным результатом исследований можно считать существование структур данных для приближенного вычисления оракула расстояния в геометрических сетях с константной протяженностью (см. теорему 4). В качестве предварительной обработки производится «усечение» сети таким образом, чтобы у нее осталось только линейное количество ребер. Структура данных состоит из серий «кластерных графов» возрастающей крупности, каждый из которых позволяет отвечать на приближенные запросы о взаимных расстояниях для пар точек в разных масштабах. Для точного нахождения кластерного графа, отвечающего на заданный запрос, структура данных использует инструмент группировки, описанный ниже. Идею использования кластерных графов для ускорения геометрических алгоритмов первыми предложили Дас и Нарасимхан [ ], позднее ее же использовали Гудмундссон и др. [8] для разработки эффективного алгоритма вычисления (1 + ")-остовов. Схожие идеи Гао и др. [7] применяли в приложениях для конструирования мобильных сетей. | |||
'''Усечение''' | |||