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

Ключевые слова и синонимы

Алгоритмы решения задач о близости на базе метрик с ограниченным ростом

Постановка задачи

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

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

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

Графы единичных дисков [4]

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

Графы единичных дисков активно использовались для моделирования коммуникаций или влияния между объектами [9, 12], а также изучались во многих других контекстах [4, 10]. К примеру, децентрализованные беспроводные сети можно эффективно моделировать при помощи графов единичных дисков [6], поскольку два беспроводных узла могут напрямую связываться друг с другом только в случае, если расстояние между ними не превышает определенного значения. В случае обучения (нейронной сети) без учителя, для плотной выборки точек из некоторого неизвестного многообразия длина кратчайшего пути в графе единичных дисков служит хорошим приближением геодезического расстояния в подлежащем (неизвестном) многообразии, если подходящим образом выбрать радиус [14, 5]. Используя декомпозицию значительно удаленных пар, можно приближенно закодировать расстояния между всеми парами вершин при помощи компактной структуры данных, поддерживающей получение приближенных ответов на запросы о расстоянии за время O(1).

Метрическое пространство

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

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

В метрическом пространстве [math]\displaystyle{ (S, \pi) \; }[/math] два непустых подмножества [math]\displaystyle{ S_1, S_2 \subseteq S \; }[/math] называются значительно удаленными с коэффициентом c, если [math]\displaystyle{ \pi (S_1, S_2) \ge c \cdot max(D_{\pi}(S_1), D_{\pi} (S_2)) \; }[/math].

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

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

• [math]\displaystyle{ A_i \cap B_i = \empty }[/math].

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

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