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

Здесь <math>|C_A C_B| \;</math> обозначает наименьшее евклидово расстояние между двумя точками в <math>C_A \;</math> и <math>C_B \;</math>, соответственно. Пример приведен на рис. 1. Пусть даны ограничивающие прямоугольники R(A)и R(B). Для проверки, являются ли множества A и B значительно удаленными относительно s, требуется всего O(d) времени.

Декомпозицию 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).