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

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