Декомпозиция на значительно удаленные пары: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 41: | Строка 41: | ||
== Основные результаты == | == Основные результаты == | ||
В работе [7] было показано, что для метрики, порожденной графом единичных дисков на n точках, и для любой константы c > 1 существует декомпозиция c-WSPD, содержащая O(nlog n) пар, и такая декомпозиция может быть найдена за время O(nlog n). Также было показано, что границы могут быть расширены на большее число размерностей. В следующих теоремах сведены основные результаты для двух и более размерностей. | |||
Теорема 1. Для любого множества точек S из n точек на плоскости и любой константы c > 1 существует декомпозиция P множества S под метрикой на графе единичных дисков, такая, что P содержит O(c4 n log n) пар и может быть вычислена за время O(c4 n log n). | |||
Теорема 2. Для любого множества точек S из n точек на плоскости в Irk для k > 3 и любой константы c > 1 существует декомпозиция P множества S под метрикой на графе единичных кругов, такая, что P содержит O(n2~2lk) пар и может быть вычислена за время O(n4/3 polylog n) для k = 3 и за время O(n2~2lk) для k > 4. | |||
Сложность получения декомпозиции значительно удаленных пар под метрикой на графе единичных дисков заключается в том, что две точки, расположенные близко друг к другу в пространстве, необязательно являются близкими в графовой метрике. Вышеприведенные границы вначале были продемонстрированы для множества точек с плотностью, ограниченной некоторой константной – т.е. множества, в котором любой единичный диск покрывает только константное число точек множества. Верхняя граница количества пар вычисляется при помощи соображения об упаковке, аналогичного приведенному в работе [8]. | |||
Для множества точек с неограниченной плотностью применяется техника кластеризации, сходная с техникой из [6], в результате чего получается множество «центральных узлов» с ограниченной плотностью. После этого к множеству центральных узлов применяется алгоритм для множеств ограниченной плотности. Наконец, для получения декомпозиции значительно удаленных пар выполняется комбинация алгоритмов декомпозиции для множеств точек с ограниченной плотностью и для евклидовой метрики. Количество пар определяется количеством пар, построенных для множества константной плотности, которое, в свою очередь, определяется границей, полученной при помощи соображения об упаковке. Было показано, что граница количества пар является строгой для k > 3. | |||
== Применение == | |||
Для пары значительно удаленных множеств расстояние между двумя точками разных множеств может быть взято приблизительно равным «расстоянию» между множествами или расстоянию между любой парой точек из разных множеств. Иными словами, декомпозицию значительно удаленных пар можно рассматривать как сжатое представление для аппроксимации &(n2) попарных расстояний. Таким образом, многие задачи, требующие проверки попарных расстояний, могут быть приближенно решены при помощи исследования расстояний между значительно удаленными парами множеств. Если декомпозиция значительно удаленных пар имеет размер ниже квадратичного, на ее основе можно получить более эффективные алгоритмы, чем простая проверка попарных расстояний. Исходя из этих соображений, декомпозиция значительно удаленных пар широко применяется в геометрических задачах. Из тех же соображений ее можно применять в различных задачах о близости под метрикой на графе единичных дисков. | |||
Предположим, что (S, d) – метрическое пространство. Пусть S1 С S. Рассмотрим следующие естественные задачи о близости. | |||
• Самый дальний сосед, диаметр, центр. Самым дальним соседом точки p 2 S1 является точка в S1, находящаяся на максимальном расстоянии от p. Родственными задачами являются задачи вычисления диаметра, максимального среди попарных кратчайших расстояний между точками в S1, а также вычисление центра – точки, максимальное расстояние от которой до всех остальных точек множества является минимальным. | |||
• Ближайший сосед, пара ближайших точек. Ближайшим соседом точки p 2 S1 является точка в S1, находящаяся на минимальном расстоянии от p. Родственными задачами являются задачи вычисления пары ближайших точек, пары с минимальным кратчайшим расстоянием, а также бихроматической пары ближайших точек – пары, для которой расстояние между точками двух разных множеств является минимальным. | |||
• Медиана. Медианой множества S является точка в S с минимальным средним (или суммарным) расстоянием до всех остальных точек. | |||
• Коэффициент растяжения. Для графа G, определенного на множестве S, коэффициентом растяжения относительно метрики на графе единичных дисков является максимальное соотношение 7Тд(р, q)/jr(p, q), где TIQ , ж – расстояния, порожденные G и графом единичных дисков, соответственно. | |||
Все вышеупомянутые задачи могут быть точно или приближенно решены для точек на евклидовой плоскости. Однако для метрик, порожденных графами (даже планарными графами), было получено относительно мало результатов, помимо решения дорогостоящей задачи нахождения кратчайших путей между всеми парами. Для вычисления диаметра существует простой метод с линейным временем выполнения, обеспечивающий 2-аппроксимацию (*), а также алгоритм 4/3-аппроксимации с временем выполнения O(mpnlogn + n2 log n) для графа с n вершинами и m ребрами, предложенный Эйнгвортом и др. [1]. | |||
2 Выберите произвольную вершину v и вычислите дерево кратчайших путей с корнем в v. Предположим, что самая дальняя от v вершина находится на расстоянии D от нее. Тогда, согласно неравенству треугольников, диаметр графа не превышает 2D. | |||
Используя декомпозицию значительно удаленных пар, Гао и Чжан [ ] показали, что можно получить более эффективную аппроксимацию вышеприведенных задач о близости для метрики на графе единичных дисков. В частности, можно получить алгоритмы с почти линейным временем выполнения для вычисления 2,42-аппроксимации и алгоритмы с временем выполнения O(npnlog n/"3) для вычисления (1 + ")-аппроксимации для любого " > 0. Кроме того, декомпозицию значительно удаленных пар можно использовать для получения оракула расстояния, требующего O(n log n/"4) объема памяти, такого, что на любой (1 + ")-запрос расстояния в графе единичных дисков можно получить ответ за время O(1). | |||
Узким местом всех вышеупомянутых алгоритмов является приближенное вычисление расстояний по кратчайшим путям между O(nlogn) парами. Алгоритм работы [7] только строит декомпозицию значительно удаленных пар, не делая подходящего приближенного вычисления расстояний. Коэффициент аппроксимации и время выполнения определяются соответствующими параметрами алгоритма аппроксимации, выполняющего оценку расстояния между каждой парой в декомпозиции значительно удаленных пар. После выполнения оценки расстояния оставшаяся часть вычисления требует почти линейного времени. | |||
Для графа общего вида неизвестно, можно ли вычислить расстояния по кратчайшим путям между O(n log n) парами значительно быстрее, чем расстояния по кратчайшим путям между всеми парами. Для планарного графа можно ли вычислить расстояния по кратчайшим путям между O(n log n) парами за время O(nnlog n), используя сепараторы размера O(pn) [ ]. Этот метод можно расширить на графы единичных дисков с ограниченной константой плотностью, поскольку такие графы удовлетворяют свойству сепараторов, аналогичного свойству для планарных графов [ ]. Что касается аппроксимации, Торуп [15] недавно предложил алгоритм для планарных графов, способный отвечать на запросы о (1 + ")-кратчайшем расстоянии за время O(1/") после выполнения предварительной обработки, требующей почти линейного времени. К сожалению, алгоритм Торупа использует сбалансированные сепараторы кратчайших путей в планарных графах, которые невозможно сходу распространить на графы единичных дисков. С другой стороны, известно, что существует планарный 2,42-остов для графа единичных дисков [11]. Применяя алгоритм Торупа к этому планарному остову, можно вычислить 2,42-аппроксимацию кратчайшего расстояния для O(nlogn) пар за почти линейное время. | |||
== Открытые вопросы == | |||
Важнейшей нерешенной проблемой является разрыв между Q(n) и O(n log n) в количестве необходимых пар на плоскости. Кроме того, временная граница (1 + ")-аппроксимации до сих пор близка к Oe(npn) из-за отсутствия эффективных способов вычисления (1 + ")-приближенных расстояний по кратчайшим путям между O(n) парами точек. Любое улучшение алгоритма решения этой задачи немедленно приведет к улучшению всех алгоритмов (1 + ")-аппроксимации, упоминавшихся выше. | |||
== См. также == | |||
* [[Применение геометрических остовных сетей]] | |||
* [[Сепараторы в графах]] | |||
* [[Разреженные остовы графов]] | |||
* [[Декомпозиция значительно удаленных пар для графа единичных дисков]] | |||
== Литература == | |||
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 | |||