Декомпозиция на значительно удаленные пары: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 56: | Строка 56: | ||
== Применение == | == Применение == | ||
Для пары значительно удаленных множеств расстояние между двумя точками разных множеств может быть взято приблизительно равным «расстоянию» между множествами или расстоянию между любой парой точек из разных множеств. Иными словами, декомпозицию на значительно удаленные пары можно рассматривать как сжатое представление для аппроксимации <math>\Theta (n^2) \;</math> попарных расстояний. Таким образом, многие задачи, требующие проверки попарных расстояний, могут быть приближенно решены при помощи исследования расстояний между значительно удаленными парами множеств. Если декомпозиция на значительно удаленные пары имеет размер ниже квадратичного, на ее основе можно получить более эффективные алгоритмы, чем простая проверка попарных расстояний. Исходя из этих соображений, декомпозиция на значительно удаленные пары | Для пары значительно удаленных множеств расстояние между двумя точками из разных множеств может быть взято приблизительно равным «расстоянию» между множествами или расстоянию между любой парой точек из разных множеств. Иными словами, декомпозицию на значительно удаленные пары можно рассматривать как сжатое представление для аппроксимации <math>\Theta (n^2) \;</math> попарных расстояний. Таким образом, многие задачи, требующие проверки попарных расстояний, могут быть приближенно решены при помощи исследования расстояний между значительно удаленными парами множеств. Если декомпозиция на значительно удаленные пары имеет размер ниже квадратичного, на ее основе можно получить более эффективные алгоритмы, чем простая проверка попарных расстояний. Исходя из этих соображений, широко применяется геометрическая декомпозиция на значительно удаленные пары. Из тех же соображений декомпозицию можно применять в различных задачах о близости под метрикой на графе единичных дисков. | ||
Предположим, что <math>(S, d) \;</math> – метрическое пространство. Пусть <math>S_1 \subseteq S</math>. Рассмотрим следующие естественные задачи о близости. | Предположим, что <math>(S, d) \;</math> – метрическое пространство. Пусть <math>S_1 \subseteq S</math>. Рассмотрим следующие естественные задачи о близости. | ||
• '''Самый дальний сосед, диаметр, центр'''. Самым дальним соседом точки <math>p \in S_1 \;</math> является точка в <math>S_1 \;</math>, находящаяся на максимальном расстоянии от p. Родственными задачами являются задачи вычисления [[диаметр|диаметра]], максимального среди попарных кратчайших расстояний между точками в S1, а также | • '''Самый дальний сосед, диаметр, центр'''. Самым дальним соседом точки <math>p \in S_1 \;</math> является точка в <math>S_1 \;</math>, находящаяся на максимальном расстоянии от p. Родственными задачами являются задачи вычисления [[диаметр|диаметра]], максимального среди попарных кратчайших расстояний между точками в S1, а также ''центра'' – точки, максимальное расстояние от которой до всех остальных точек множества является минимальным. | ||
• '''Ближайший сосед, пара ближайших точек'''. Ближайшим соседом точки <math>p \in S_1 \;</math> является точка в <math>S_1 \;</math>, находящаяся на минимальном расстоянии от p. Родственными задачами являются задачи вычисления ''пары ближайших точек'', то есть пары с минимальным кратчайшим расстоянием, а также ''бихроматической пары ближайших точек'' – пары, для которой расстояние между точками двух разных множеств является минимальным. | • '''Ближайший сосед, пара ближайших точек'''. Ближайшим соседом точки <math>p \in S_1 \;</math> является точка в <math>S_1 \;</math>, находящаяся на минимальном расстоянии от p. Родственными задачами являются задачи вычисления ''пары ближайших точек'', то есть пары с минимальным кратчайшим расстоянием, а также ''бихроматической пары ближайших точек'' – пары, для которой расстояние между точками двух разных множеств является минимальным. | ||