Декомпозиция на значительно удаленные пары: различия между версиями

Используя декомпозицию на значительно удаленные пары, Гао и Чжан [7] показали, что можно получить более эффективные алгоритмы аппроксимации вышеприведенных задач о близости для метрики на графе единичных дисков. В частности, можно получить алгоритмы с почти линейным временем выполнения для вычисления 2,42-аппроксимации и алгоритмы с временем выполнения <math>O(n \sqrt{n \; log \; n} / \varepsilon^3)</math> для вычисления <math>(1 + \varepsilon) \;</math>-аппроксимации для любого <math>\varepsilon > 0 \;</math>. Кроме того, декомпозицию на значительно удаленные пары можно использовать для получения оракула расстояния, требующего <math>O(n \; log \; n / \varepsilon^4)</math> объема памяти, такого, что на любой <math>(1 + \varepsilon) \;</math>-запрос расстояния в графе единичных дисков можно получить ответ за время O(1).

Узким местом всех вышеупомянутых алгоритмов является приближенное вычисление расстояний по кратчайшим путям между O(n log n) парами. Алгоритм работы [7] только строит декомпозицию на значительно удаленные пары, не делая подходящего приближенного вычисления расстояний. Коэффициент аппроксимации и время выполнения определяются соответствующими параметрами алгоритма аппроксимации, используемого для оценки расстояния между каждой парой в декомпозиции на значительно удаленные пары. После выполнения оценки расстояния оставшаяся часть вычисления требует почти линейного времени.