Прямолинейное остовное дерево: различия между версиями

Для каждой точки s необходимо найти ближайшего к ней соседа в каждом октанте. Опишем, как эффективно вычислить соседей в октанте <math>R_1 \;</math> для всех точек. Случаи остальных октантов симметричны. Для октанта <math>R_1 \;</math> алгоритм с заметающей прямой исполняется для всех точек в порядке неубывания x + y. В процессе заметания поддерживается [[активное множество]], состоящее из точек, для которых ближайшие соседи в <math>R_1 \;</math> еще не найдены. После обработки точки p будут найдены все точки активного множества, содержащие p в их областях <math>R_1 \;</math>. Если такая точка содержится в активном множестве, то, поскольку точки проверяются в порядке неубывания x + y, p должна быть ближайшей точкой для s в <math>R_1 \;</math>. Таким образом, будет добавлено ребро sp и точка s будет удалена из активного множества. После обработки этих активных точек точка p будет добавлена в активное множество. Каждая точка будет добавлена в активное множество и удалена из него только один раз.

Чтобы найти подмножество активных точек, для которых s находится в их областях <math>R_1 \;</math>, вначале необходимо найти наибольшее x, такое, что <math>x \le x_s \;</math>, а затем выполнять обработку в порядке убывания x, до тех пор, пока не будет достигнуто <math>x - y \ge x_s - y_s \;</math>. Поскольку упорядочение производится только по одному измерению, используя любое бинарное дерево поиска со стоимостью операций вставки, деления и запроса, равной O(log n), получаем алгоритм с временем исполнения O(n log n). Бинарные деревья поиска также требуют балансировки. Кроме того, можно использовать списки с пропусками [2], использующие рандомизацию во избежание проблемы явной балансировки, но демонстрирующие ожидаемое поведение на уровне O(log n).

Экспериментальные результаты построения прямолинейного остовного графа (ПОГ) на основе алгоритма Крускала для вычисления прямолинейного МОД были представлены Чжоу и др. [5]. В сравнении участвовали два других подхода. Первый подход использовал полный граф на множестве точек в качестве входного для алгоритма Крускала. Второй подход представлял собой реализацию концепции, предложенной в [3]: для каждой точки просканировать все остальные точки, но соединить ее только с ближайшей точкой в каждом квадранте. В эксперименте использовались множества от 1000 до 20000 точек, сгенерированные случайным образом. Результаты эксперимента представлены в таблице 1. В первом столбце указано количество сгенерированных точек; во втором – количество различающихся точек. Для каждого подхода приведены количество ребер в заданном графе и общее время исполнения. Если количество точек на входе было больше 10000, подходу на основе полного графа попросту не хватало памяти.