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

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

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

== Нотация и определения ==