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

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

Для графа общего вида неизвестно, можно ли вычислить расстояния по кратчайшим путям между O(n log n) парами значительно быстрее, чем расстояния по кратчайшим путям между всеми парами. Для планарного графа можно ли вычислить расстояния по кратчайшим путям между O(n log n) парами за время <math>O(n \sqrt{n \; log \; n})</math>, используя сепараторы размера <math>O( \sqrt{n}) \;</math> [2]. Этот метод можно расширить на графы единичных дисков с ограниченной константой плотностью, поскольку такие графы удовлетворяют свойству [[Сепараторы в графах|сепараторов]], аналогичному свойству для планарных графов [13]. Что касается аппроксимации, Торуп [15] недавно предложил алгоритм для планарных графов, способный отвечать на запросы о <math>(1 + \varepsilon) \;</math>-кратчайшем расстоянии за время <math>O(1 / \varepsilon) \;</math> после выполнения предварительной обработки, требующей почти линейного времени. К сожалению, алгоритм Торупа использует сбалансированные сепараторы кратчайших путей в планарных графах, которые невозможно сходу распространить на графы единичных дисков. С другой стороны, известно, что существует планарный 2,42-остов для графа единичных дисков [11]. Применяя алгоритм Торупа к этому планарному остову, можно вычислить 2,42-аппроксимацию кратчайшего расстояния для O(n log n) пар за почти линейное время.

Важнейшей нерешенной проблемой является разрыв между <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>-аппроксимации, упоминавшихся выше.