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

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

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

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

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

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

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

Графы единичных дисков [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{ min_{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 , 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 квадратичного размера в виде тривиального семейства, содержащего все попарные комбинации элементов.

Основные результаты

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

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

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

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

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

Применение

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

Предположим, что [math]\displaystyle{ (S, d) \; }[/math] – метрическое пространство. Пусть [math]\displaystyle{ S_1 \subseteq S }[/math]. Рассмотрим следующие естественные задачи о близости.

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

• Ближайший сосед, пара ближайших точек. Ближайшим соседом точки [math]\displaystyle{ p \in S_1 \; }[/math] является точка в [math]\displaystyle{ S_1 \; }[/math], находящаяся на минимальном расстоянии от p. Родственными задачами являются задачи вычисления пары ближайших точек, то есть пары с минимальным кратчайшим расстоянием, а также бихроматической пары ближайших точек – пары, для которой расстояние между точками двух разных множеств является минимальным.

• Медиана. Медианой множества S является точка в S с минимальным средним (или суммарным) расстоянием до всех остальных точек.

• Коэффициент растяжения. Для графа G, определенного на множестве S, коэффициентом растяжения относительно метрики на графе единичных дисков является максимальное соотношение [math]\displaystyle{ \pi_G (p, q) / \pi(p, q) \; }[/math], где [math]\displaystyle{ \pi_G, \pi \; }[/math] – расстояния, порожденные G и графом единичных дисков, соответственно.

Все вышеупомянутые задачи могут быть точно или приближенно решены для точек на евклидовой плоскости. Однако для метрик, порожденных графами (даже планарными графами), было получено относительно мало результатов, помимо решения дорогостоящей задачи нахождения кратчайших путей между всеми парами. Для вычисления диаметра существует простой метод с линейным временем выполнения, обеспечивающий 2-аппроксимацию (*), а также алгоритм 4/3-аппроксимации с временем выполнения [math]\displaystyle{ O(m \sqrt{n \; log \; n} + n^2 \; log \; n) }[/math] для графа с n вершинами и m ребрами, предложенный Эйнгвортом и др. [1].

(*) Выберите произвольную вершину v и вычислите дерево кратчайших путей с корнем в v. Предположим, что самая дальняя от v вершина находится на расстоянии D от нее. Тогда, согласно неравенству треугольников, диаметр графа не превышает 2D.

Используя декомпозицию на значительно удаленные пары, Гао и Чжан [7] показали, что можно получить более эффективные аппроксимационные алгоритмы вышеприведенных задач о близости для метрики на графе единичных дисков. В частности, можно получить алгоритмы с почти линейным временем выполнения для вычисления 2,42-аппроксимации и алгоритмы с временем выполнения [math]\displaystyle{ O(n \sqrt{n \; log \; n} / \varepsilon^3) }[/math] для вычисления [math]\displaystyle{ (1 + \varepsilon) \; }[/math]-аппроксимации для любого [math]\displaystyle{ \varepsilon \gt 0 \; }[/math]. Кроме того, декомпозицию на значительно удаленные пары можно использовать для получения оракула расстояния, требующего [math]\displaystyle{ O(n \; log \; n / \varepsilon^4) }[/math] объема памяти, такого, что на любой [math]\displaystyle{ (1 + \varepsilon) \; }[/math]-запрос расстояния в графе единичных дисков можно получить ответ за время O(1).

Узким местом всех вышеупомянутых алгоритмов является приближенное вычисление расстояний по кратчайшим путям между O(n log n) парами. Алгоритм работы [7] только строит декомпозицию на значительно удаленные пары, не делая подходящего приближенного вычисления расстояний. Коэффициент аппроксимации и время выполнения определяются соответствующими параметрами аппроксимационного алгоритма, используемого для оценки расстояния между каждой парой в декомпозиции на значительно удаленные пары. После выполнения оценки расстояния оставшаяся часть вычисления требует почти линейного времени.

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

Открытые вопросы

Важнейшей нерешенной проблемой является разрыв между [math]\displaystyle{ \Omega(n) \; }[/math] и [math]\displaystyle{ O(n \; log \; n) }[/math] в количестве необходимых пар на плоскости. Кроме того, временная граница [math]\displaystyle{ (1 + \varepsilon) \; }[/math]-аппроксимации до сих пор близка к [math]\displaystyle{ \tilde{O} (n \sqrt{n}) }[/math] из-за отсутствия эффективных способов вычисления [math]\displaystyle{ (1 + \varepsilon) \; }[/math]-приближенных расстояний по кратчайшим путям между O(n) парами точек. Любое улучшение алгоритма решения этой задачи немедленно приведет к улучшению всех алгоритмов [math]\displaystyle{ (1 + \varepsilon) \; }[/math]-аппроксимации, упоминавшихся выше.

См. также

• Применение геометрических остовных сетей
• Сепараторы в графах
• Разреженные остовы графов
• Декомпозиция на значительно удаленные пары для графа единичных дисков

Литература

1. Aingworth, D., Chekuri, C., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). In: Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, 1996, pp.547-553

2. Arikati, S.R., Chen, D.Z., Chew, L.P., Das, G., Smid, M.H.M., Zaroliagis, C.D: Planar spanners and approximate shortest path queries among obstacles in the plane. In: Dfaz, J., Serna, M. (eds.) Proc. of 4th Annual European Symposium on Algorithms, 1996, pp. 514-528

3. Callahan, P.B., Kosaraju, S. R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42,67-90 (1995)

4. Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discret. Math. 86,165-177(1990)

5. Fischl, B., Sereno, M., Dale, A.: Cortical surface-based analysis II: Inflation, flattening, and a surface-based coordinate system. NeuroImage 9,195-207 (1999)

6. Gao, J., Guibas, L.J., Hershberger, J., Zhang, L., Zhu, A.: Geometric spanners for routing in mobile networks. IEEE J. Sel. Areas Commun. Wirel. Ad Hoc Netw. (J-SAC), 23(1), 174-185 (2005)

7. Gao, J., Zhang, L.: Well-separated pair decomposition for the unit-disk graph metric and its applications. In: Proc. of 35th ACM Symposium on Theory of Computing (STOC'03), 2003, pp. 483-492

8. Guibas, L., Ngyuen, A., Russel, D., Zhang, L.: Collision detection for deforming necklaces. In: Proc. 18th ACM Symposium on Computational Geometry, 2002, pp. 33^2

9. Hale, W. K.: Frequency assignment: Theory and applications. Proc. IEEE. 68(12), 1497-1513 (1980)

10. H.B.H. III, Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithms 26(2), 238-274 (1998)

11. Li, X.Y., Calinescu, G., Wan, P.J.: Distributed Construction of a Planar Spanner and Routing for Ad Hoc Wireless Networks. In: IEEE INFOCOM 2002, New York, NY, 23-27 June 2002

12. Mead, C.A., Conway, L.: Introduction to VLSI Systems. Addison-Wesley, (1980)

13. Miller, G.L., Teng, S.H., Vavasis, S.A.: An unified geometric approach to graph separators. In: Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci. 1991, pp. 538-547

14. Tenenbaum, J., de Silva, V., Langford, J.: A global geometric framework for nonlinear dimensionality reduction. Science 290, 22 (2000)

15. Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. In: Proc. 42nd IEEE Symposium on Foundations of Computer Science, 2001, pp. 242-251