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

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

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

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

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

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

Сложность получения декомпозиции значительно удаленных пар под метрикой на графе единичных дисков заключается в том, что две точки, расположенные близко друг к другу в пространстве, необязательно являются близкими в графовой метрике. Вышеприведенные границы вначале были продемонстрированы для множества точек с плотностью, ограниченной некоторой константой – т.е. множества, в котором любой единичный диск покрывает только константное число точек множества. Верхняя граница количества пар вычисляется при помощи соображения об упаковке, аналогичного приведенному в работе [8].

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

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

* [[Декомпозиция значительно удаленных пар для графа единичных дисков]]