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

Алгоритм Агарвала и коллег базируется на исследовании отношений между вычислением MST и нахождением ближайшей пары среди n красных точек и m синих точек (вторая задача носит название задачи нахождения бихроматической пары ближайших точек). Они показали, что если обозначить за <math>T_d(n, m) \;</math> время, необходимое для решения второй задачи, то задача MST может быть решена за время <math>O(T_d (n, n)log^d n) \;</math>. Позднее Кэллахан и Косарайю [4] улучшили это время до <math>O(T_d (n, n) log \; n)</math>. Оба метода демонстрируют время исполнения <math>O(T_d (n, n)) \;</math>, если <math>T_d(n, n) = \Omega (n^{l + \alpha}) \;</math> для некоторого <math>\alpha > 0 \;</math>. Наконец, Кржнарик и коллеги [10] показали, что эти две задачи (нахождение MST и вычисление бихроматической пары ближайших точек) имеют одну и ту же временную сложность в наихудшем случае, с поправкой на константный множитель, в рамках наиболее часто используемой модели алгебраического дерева вычислений и для любой фиксированной <math>L_p</math>-метрики. Сложнее всего доказать, что задача MST может быть решена за время <math>O(T_d(n, n)) \;</math>. Второй аспект проблемы – доказательство того, что найти бихроматическую пару ближайших точек не сложнее, чем вычислить MST – намного проще: если вначале вычислить MST для объединения n + m синих и красных точек, после этого найти ближайшую бихроматическую пару можно за линейное время, поскольку по меньшей мере одна такая пара должна быть соединена некоторым ребром MST.

Предположим, что следующее ребро, которое собирается создать алгоритм, имеет длину l. Каждое дерево T в лесу подразделяется на группы вершин, каждую из которых представляет одна конкретная вершина. Вершина-представитель такой группы называется ее ''лидером''. Далее, каждая вершина в группе, включая лидера, обладает следующим свойством: она находится от лидера на расстоянии не более <math>\epsilon \cdot l \;</math>, где <math>\epsilon \;</math> – вещественная константа, близкая к нулю.