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

Понятие декомпозиции на значительно удаленные пары, предложенное Кэллаханом и Косарайю [3], нашло широкое применение при решении задач о близости точек на евклидовой плоскости. Пара множеств точек (A, B) является ''значительно удаленной с коэффициентом c'', если расстояние между A и B не менее чем в c раз превышает диаметры A и B. Декомпозиция на значительно удаленные пары для множества точек состоит из множества значительно удаленных пар, «покрывающих» все пары различных точек; иначе говоря, любые две различные точки принадлежат к разным множествам некоторой пары. Кэллахан и Косарайю [3] показали, что для любого множества точек на евклидовой плоскости и любой константы c <math>\ge 1 \;</math> всегда существует декомпозиция на значительно удаленные пары с коэффициентом c (c-WSPD) с линейным числом пар. Этот факт оказался исключительно полезным для разработки алгоритмов с близким к линейному временем выполнения для решения самых разных задач – таких как вычисление k-ближайших соседей, потенциальных полей для системы из N тел, геометрических остовов, приближенных минимальных остовных деревьев и многих других. Декомпозиция на значительно удаленные пары также широко использовалась для разработки эффективных динамических и параллельных алгоритмов, а также алгоритмов на базе внешней памяти.

Определение декомпозиции на значительно удаленные пары может быть естественным образом расширено на любое метрическое пространство. Однако в метрических пространствах общего вида декомпозиция на значительно удаленные пары с размером ниже квадратичного может оказаться невозможной. И в самом деле, для метрики, порожденной звездчатым деревом с единичным весом каждого ребра 1, любая декомпозиция на значительно удаленные пары требует квадратичного числа пар. По этой причине для подобной метрики она не имеет практического смысла. Тем не менее, было показано, что для метрики на основе графов единичных дисков существуют алгоритмы декомпозиции на значительно удаленные пары с близким к линейному размером и, следовательно, многие задачи о близости на базе этой метрики могут быть эффективно решены при помощи этого подхода.

1 Метрика, порожденная графом (с положительными весами ребер), представляет собой метрику на основе кратчайшего пути по графу.  

Обозначим за d(<math>\cdot, \cdot</math>) евклидову метрику. Для множества точек S на плоскости графом единичных дисков I(S) = (S, E) является взвешенный граф, для которого ребро e = (p, q) принадлежит графу, если <math>d(p, q) \le 1 \;</math>, а вес ребра e равен d(p, q). Аналогичным образом можно определить граф единичных шаров для точек в пространстве более высокой размерности.

Рассмотрим метрическое пространство <math>(S, \pi) \;</math>, где <math>S \;</math> – множество элементов, а <math>\pi \;</math> – функция расстояния, определенная на <math>S \times S \;</math>. Для любого подмножества <math>S_1 \subseteq S \;</math> [[диаметр]] <math>D_{\pi}(S_1) \;</math> (или <math>D(S_1) \;</math>, если <math>\pi \;</math> очевидно из контекста) множества <math>S \;</math> определяется как <math>max_{s_1, s_2 \in S_1} \; \pi (s_1, s_2)</math>. ''Расстояние'' <math>\pi(S_1, S_2) \;</math> между двумя множествами <math>S_1, S_2 \subseteq S \;</math> определяется как <math>max_{s_1 \in S_1, s_2 \in S_2} \; \pi (s_1, s_2)</math>.

Согласно определению в [3], для любых двух множеств A и B множество пар <math>\mathcal{P} = \{ P_1, P_2, ..., P_m \} \;</math>, где <math>P_i = (A_i, B_i) \;</math>, называется попарной [[Decomposition|декомпозицией]] (A, B) (или A, если A = B) в случае, если

• Для всех значений индексов i верно <math>A_i \subseteq A \;</math>, <math>B_i \subseteq B</math>.

• <math>A_i \cap B_i = \empty</math>.

• Для любых двух элементов <math>a \in A, b \in B \;</math> существует уникальный индекс i, такой, что <math>a \in A_i, b \in B_i \;</math>. Будем говорить, что (a, b) ''покрыты'' парой <math>(A_i, B_i) \;</math>.

Если при этом каждая пара в <math>\mathcal{P}</math> является значительно удаленной с коэффициентом c, <math>\mathcal{P}</math> называется ''декомпозицией на значительно удаленные пары с коэффициентом c'' (или, для краткости, c-WSPD). Очевидно, что любое метрическое пространство поддерживает c-WSPD квадратичного размера, которое можно получить путем использования тривиального семейства, содержащего все попарные комбинации элементов.

В работе [7] было показано, что для метрики, порожденной графом единичных дисков на n точках, и для любой константы <math>c \ge 1 \;</math> существует декомпозиция c-WSPD, содержащая O(n log n) пар, и такая декомпозиция может быть найдена за время O(n log n). Также было показано, что границы могут быть расширены на большее число размерностей. В следующих теоремах сведены основные результаты для двух и более размерностей.

'''Теорема 1. Для любого множества точек S из n точек на плоскости и любой константы <math>c \ge 1 \;</math> существует декомпозиция <math>\mathcal{P}</math> множества S под метрикой на графе единичных дисков, такая, что <math>\mathcal{P}</math> содержит <math>O(c^4 \; n \; log \; n)</math> пар и может быть вычислена за время <math>O(c^4 \; n \; log \; n)</math>.'''

'''Теорема 2. Для любого множества точек S из n точек на плоскости в <math>\mathbb{R}^k</math> для <math>k \ge 3 \;</math> и любой константы <math>c \ge 1 \;</math> существует декомпозиция <math>\mathcal{P}</math> множества S под метрикой на графе единичных кругов, такая, что <math>\mathcal{P}</math> содержит <math>O(n^{2 - 2/k}) \;</math> пар и может быть вычислена за время <math>O(n^{4/3} \; polylog \; n)</math> для k = 3 и за время <math>O(n^{2 - 2/k}) \;</math> для <math>k \ge 4 \;</math>.'''

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

Для пары значительно удаленных множеств расстояние между двумя точками разных множеств может быть взято приблизительно равным «расстоянию» между множествами или расстоянию между любой парой точек из разных множеств. Иными словами, декомпозицию на значительно удаленные пары можно рассматривать как сжатое представление для аппроксимации <math>\Theta (n^2) \;</math> попарных расстояний. Таким образом, многие задачи, требующие проверки попарных расстояний, могут быть приближенно решены при помощи исследования расстояний между значительно удаленными парами множеств. Если декомпозиция на значительно удаленные пары имеет размер ниже квадратичного, на ее основе можно получить более эффективные алгоритмы, чем простая проверка попарных расстояний. Исходя из этих соображений, декомпозиция на значительно удаленные пары широко применяется в геометрических задачах. Из тех же соображений ее можно применять в различных задачах о близости под метрикой на графе единичных дисков.

• '''Самый дальний сосед, диаметр, центр'''. Самым дальним соседом точки <math>p \in S_1 \;</math> является точка в <math>S_1 \;</math>, находящаяся на максимальном расстоянии от p. Родственными задачами являются задачи вычисления [[диаметр|диаметра]], максимального среди попарных кратчайших расстояний между точками в S1, а также вычисление ''центра'' – точки, максимальное расстояние от которой до всех остальных точек множества является минимальным.

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