4488
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 21: | Строка 21: | ||
Здесь <math>|C_A C_B| \;</math> обозначает наименьшее евклидово расстояние между двумя точками в <math>C_A \;</math> и <math>C_B \;</math>, соответственно. Пример приведен на рис. 1. Пусть даны ограничивающие прямоугольники R(A)и R(B). Для проверки, являются ли множества A и B значительно удаленными относительно s, требуется всего O(d) времени. | Здесь <math>|C_A C_B| \;</math> обозначает наименьшее евклидово расстояние между двумя точками в <math>C_A \;</math> и <math>C_B \;</math>, соответственно. Пример приведен на рис. 1. Пусть даны ограничивающие прямоугольники R(A)и R(B). Для проверки, являются ли множества A и B значительно удаленными относительно s, требуется всего O(d) времени. | ||
[[Файл:WSPD_UDG.png]] | |||
Рисунок 1. Множества A и B являются значительно удаленными относительно s | |||
Строка 51: | Строка 56: | ||
Декомпозицию S на значительно удаленные пары относительно заданного коэффициента удаленности s теперь можно получить из T(S) следующим образом. Для каждой внутренней вершины T(S) с потомками v и w вызывается следующая рекурсивная процедура FindPairs(v, w). Если <math>S_v \;</math> и <math>S_w \;</math> являются значительно удаленными, то процедура выдает результат <math>(S_v, S_w) \;</math>. В противном случае предположим, что наибольшее измерение <math>R(S_v) \;</math> превышает по длине наибольшее измерение <math>R(S_w) \;</math> и что <math>v_l, v_r \;</math> являются вершинами-потомками v в дереве T(S). После этого вызываются процедуры FindPairs(<math>v_l</math>, w) и FindPairs(<math>v_r</math>, w). | Декомпозицию S на значительно удаленные пары относительно заданного коэффициента удаленности s теперь можно получить из T(S) следующим образом. Для каждой внутренней вершины T(S) с потомками v и w вызывается следующая рекурсивная процедура FindPairs(v, w). Если <math>S_v \;</math> и <math>S_w \;</math> являются значительно удаленными, то процедура выдает результат <math>(S_v, S_w) \;</math>. В противном случае предположим, что наибольшее измерение <math>R(S_v) \;</math> превышает по длине наибольшее измерение <math>R(S_w) \;</math> и что <math>v_l, v_r \;</math> являются вершинами-потомками v в дереве T(S). После этого вызываются процедуры FindPairs(<math>v_l</math>, w) и FindPairs(<math>v_r</math>, w). | ||
правок