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

Эта структура данных также может быть применена к некоторым другим задачам, среди которых можно упомянуть (1) задачу нахождения приближенного ответа на запросы о расстоянии между вершинами в планарной многоугольной области с «скругленными» препятствиями, (2) варианты запросов о нахождении пар ''ближайших точек'' и (3) эффективное вычисление приближенной протяженности геометрических графов.

Над разработкой эффективных структур данных для ответа на запросы о расстоянии для сетей общего вида (не геометрических) работали Торуп и Цвик [15] (они рассматривали невзвешенные графы общего вида), Басванна и Сен [3] (взвешенные графы общего вида, то есть произвольные метрики), а также Арикати и др. [2] и Торуп [14] (взвешенные планарные графы).