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

Для множества точек с неограниченной плотностью применяется техника кластеризации, сходная с техникой из [6], результатом применения которой оказывается множество «центральных узлов» с ограниченной плотностью. После этого к множеству центральных узлов применяется алгоритм для множеств ограниченной плотности. Наконец, для получения декомпозиции на значительно удаленные пары выполняется комбинация алгоритмов декомпозиции для множеств точек с ограниченной плотностью и для евклидовой метрики. Количество пар финальной декомпозиции определяется количеством пар, построенных для множества константной плотности, которое, в свою очередь, определяется границей, полученной при помощи соображения об упаковке. Было показано, что граница количества пар является строгой для <math>k \ge 3 \;</math>.

Используя декомпозицию на значительно удаленные пары, Гао и Чжан [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] только строит декомпозицию на значительно удаленные пары, не делая подходящего приближенного вычисления расстояний. Коэффициент аппроксимации и время выполнения определяются соответствующими параметрами алгоритма аппроксимации, используемого для оценки расстояния между каждой парой в декомпозиции на значительно удаленные пары. После выполнения оценки расстояния оставшаяся часть вычисления требует почти линейного времени.

Важнейшей нерешенной проблемой является разрыв между <math>\Omega(n) \;</math> и O(n log n) в количестве необходимых пар на плоскости. Кроме того, временная граница <math>(1 + \varepsilon) \;</math>-аппроксимации до сих пор близка к <math>\tilde{O} (n \sqrt{n})</math> из-за отсутствия эффективных способов вычисления <math>(1 + \varepsilon) \;</math>-приближенных расстояний по кратчайшим путям между O(n) парами точек. Любое улучшение алгоритма решения этой задачи немедленно приведет к улучшению всех алгоритмов <math>(1 + \varepsilon) \;</math>-аппроксимации, упоминавшихся выше.