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

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