Применение геометрических остовных сетей

Ключевые слова и синонимы

Коэффициент растяжения

Постановка задачи

Пусть дан геометрический граф в d-мерном пространстве. Было бы полезно предварительно обработать его таким образом, чтобы можно было эффективно отвечать на запросы о расстояниях (точно или приближенно). Алгоритмы, которые могут отвечать на запросы о расстояниях за константное время, называются также «оракулами расстояния». Очевидно, что при неограниченном времени и памяти для предварительной обработки легко можно построить точные оракулы расстояния. Далее будет рассмотрена разработка приближенных оракулов расстояния при ограниченных значениях времени и памяти для предварительной обработки для семейства геометрических графов с константной протяженностью.