Применение геометрических остовных сетей: различия между версиями

Основным результатом исследований можно считать существование структур данных для приближенного вычисления оракула расстояния в геометрических сетях с константной протяженностью (см. теорему 4). В качестве предварительной обработки производится «усечение» сети таким образом, чтобы у нее осталось только линейное количество ребер. Структура данных состоит из серий «кластерных графов» возрастающей крупности, каждый из которых позволяет отвечать на приближенные запросы о взаимных расстояниях для пар точек в разных масштабах. Для точного нахождения кластерного графа, отвечающего на заданный запрос, структура данных использует инструмент группировки, описанный ниже. Идею использования кластерных графов для ускорения геометрических алгоритмов первыми предложили Дас и Нарасимхан [ ], позднее ее же использовали Гудмундссон и др. [8] для разработки эффективного алгоритма вычисления (1 + ")-остовов. Схожие идеи Гао и др. [7] применяли в приложениях для конструирования мобильных сетей.

Теорема 1. Пусть t > 1 и "0 > 0 – вещественные константы. Пусть S – множество из n точек в пространстве Rd, а G = (S, E) – t-остов для S, имеющий m ребер. Существует алгоритм, за время O(m + nlog n) вычисляющий (1 + "0)-остов G, имеющий O(n) ребер и вес O(wt(MST(S))).