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

Для пары значительно удаленных множеств расстояние между двумя точками разных множеств может быть взято приблизительно равным «расстоянию» между множествами или расстоянию между любой парой точек из разных множеств. Иными словами, декомпозицию значительно удаленных пар можно рассматривать как сжатое представление для аппроксимации &(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 и графом единичных дисков, соответственно.