4551
правка
Декомпозиция на значительно удаленные пары: различия между версиями
Перейти к навигации
Перейти к поиску
Декомпозиция на значительно удаленные пары (посмотреть исходный код)
Версия от 11:58, 6 марта 2018
, 6 марта 2018→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Алгоритмы решения задач о близости на базе метрик с ограни…») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Понятие декомпозиции значительно удаленных пар, предложенное Кэллаханом и Косарайю [3], нашло широкое применение при решении задач о близости точек на евклидовой плоскости. Пара множеств точек (A, B) является значительно удаленной с коэффициентом c, если расстояние между A и B не менее чем в c раз превышает диаметры A и B. Декомпозиция значительно удаленных пар для множества точек состоит из множества значительно удаленных пар, «покрывающих» все пары различных точек; иначе говоря, любые две различные точки принадлежат к разным множествам некоторой пары. Кэллахан и Косарайю [3] показали, что для любого множества точек на евклидовой плоскости и любой константы c > 1 всегда существует декомпозиция значительно удаленных пар с коэффициентом c (c-WSPD) с линейным числом пар. Этот факт оказался исключительно полезным для разработки алгоритмов с близким к линейному временем выполнения для решения самых разных задач – таких как вычисление k-ближайших соседей, потенциальных полей для системы из N тел, геометрических остовов, приближенных минимальных остовных деревьев и многих других. Декомпозиция значительно удаленных пар также широко использовалась для разработки эффективных динамических и параллельных алгоритмов, а также алгоритмов на базе внешней памяти. | Понятие декомпозиции значительно удаленных пар, предложенное Кэллаханом и Косарайю [3], нашло широкое применение при решении задач о близости точек на евклидовой плоскости. Пара множеств точек (A, B) является ''значительно удаленной с коэффициентом c'', если расстояние между A и B не менее чем в c раз превышает диаметры A и B. Декомпозиция значительно удаленных пар для множества точек состоит из множества значительно удаленных пар, «покрывающих» все пары различных точек; иначе говоря, любые две различные точки принадлежат к разным множествам некоторой пары. Кэллахан и Косарайю [3] показали, что для любого множества точек на евклидовой плоскости и любой константы c <math>\ge 1 \;</math> всегда существует декомпозиция значительно удаленных пар с коэффициентом c (c-WSPD) с линейным числом пар. Этот факт оказался исключительно полезным для разработки алгоритмов с близким к линейному временем выполнения для решения самых разных задач – таких как вычисление k-ближайших соседей, потенциальных полей для системы из N тел, геометрических остовов, приближенных минимальных остовных деревьев и многих других. Декомпозиция значительно удаленных пар также широко использовалась для разработки эффективных динамических и параллельных алгоритмов, а также алгоритмов на базе внешней памяти. | ||
| Строка 13: | Строка 13: | ||
'''Графы единичных дисков [4]''' | '''Графы единичных дисков [4]''' | ||
Обозначим за d( | Обозначим за d(<math>\cdot, \cdot</math>) евклидову метрику. Для множества точек S на плоскости графом единичных дисков I(S) = (S, E) является взвешенный граф, для которого ребро e = (p, q) принадлежит графу, если <math>d(p, q) \le 1 \;</math>, а вес ребра e равен d(p, q). Аналогичным образом можно определить граф единичных шаров для точек в пространстве более высокой размерности. | ||
Графы единичных дисков активно использовались для моделирования коммуникаций или влияния между объектами [9, 12], а также изучались во многих других контекстах [4, 10]. К примеру, децентрализованные беспроводные сети можно эффективно моделировать при помощи графов единичных дисков [ ], поскольку два беспроводных узла могут напрямую связываться друг с другом только в случае, если расстояние между ними не превышает определенного значения. В случае обучения (нейронной сети) без учителя, для плотной выборки точек из некоторого неизвестного многообразия длина кратчайшего пути в графе единичных дисков служит хорошим приближением геодезического расстояния в подлежащем (неизвестном) многообразии, если подходящим образом выбрать радиус [14, 5]. Используя декомпозицию значительно удаленных пар, можно приближенно закодировать расстояния между всеми парами вершин при помощи компактной структуры данных, поддерживающей получение приближенных ответов на запросы о расстоянии за время O(1). | Графы единичных дисков активно использовались для моделирования коммуникаций или влияния между объектами [9, 12], а также изучались во многих других контекстах [4, 10]. К примеру, децентрализованные беспроводные сети можно эффективно моделировать при помощи графов единичных дисков [6], поскольку два беспроводных узла могут напрямую связываться друг с другом только в случае, если расстояние между ними не превышает определенного значения. В случае обучения (нейронной сети) без учителя, для плотной выборки точек из некоторого неизвестного многообразия длина кратчайшего пути в графе единичных дисков служит хорошим приближением геодезического расстояния в подлежащем (неизвестном) многообразии, если подходящим образом выбрать радиус [14, 5]. Используя декомпозицию значительно удаленных пар, можно приближенно закодировать расстояния между всеми парами вершин при помощи компактной структуры данных, поддерживающей получение приближенных ответов на запросы о расстоянии за время O(1). | ||
'''Метрическое пространство''' | '''Метрическое пространство''' | ||
Рассмотрим метрическое пространство (S, | Рассмотрим метрическое пространство <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>. | ||