4551
правка
Прямолинейное остовное дерево: различия между версиями
Материал из WEGA
Прямолинейное остовное дерево (посмотреть исходный код)
Версия от 14:33, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 48: | Строка 48: | ||
Пусть даны две точки p, q в одном и том же сегменте (октанте) восьмиугольного разбиения плоскости относительно точки s. Согласно свойству единственности, ||pq|| < max(||sp||; ||sq||). Рассмотрим цикл с точками s, p и q. Согласно свойству циклов, только одну точку с минимальным расстоянием до s необходимо соединить с s. Интересное свойство восьмиугольного разбиения заключается в том, что контур равноудаленных от s точек формирует отрезок прямой в каждой области. В областях <math>R_1, R_2, R_5, R_6 \;</math> эти сегменты описываются уравнением вида x + y = c; в областях <math>R_3, R_4, R_7, R_8 \;</math> – уравнением вида x - y = c. | Пусть даны две точки p, q в одном и том же сегменте (октанте) восьмиугольного разбиения плоскости относительно точки s. Согласно свойству единственности, ||pq|| < max(||sp||; ||sq||). Рассмотрим цикл с точками s, p и q. Согласно свойству циклов, только одну точку с минимальным расстоянием до s необходимо соединить с s. Интересное свойство восьмиугольного разбиения заключается в том, что контур равноудаленных от s точек формирует отрезок прямой в каждой области. В областях <math>R_1, R_2, R_5, R_6 \;</math> эти сегменты описываются уравнением вида x + y = c; в областях <math>R_3, R_4, R_7, R_8 \;</math> – уравнением вида x - y = c. | ||
Для каждой точки s необходимо найти ближайшего к ней соседа в каждом октанте. Опишем, как эффективно вычислить соседей в октанте <math>R_1 \;</math> для всех точек. Случаи остальных октантов симметричны. Для октанта <math>R_1 \;</math> алгоритм с заметающей прямой | Для каждой точки 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 будет добавлена в активное множество. Каждая точка будет добавлена в активное множество и удалена из него только один раз. | ||
| Строка 60: | Строка 60: | ||
Чтобы найти подмножество активных точек, для которых 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), получаем алгоритм с временем | Чтобы найти подмножество активных точек, для которых 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). | ||
| Строка 99: | Строка 99: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Экспериментальные результаты построения прямолинейного остовного графа (ПОГ) на основе алгоритма Крускала для вычисления прямолинейного МОД были представлены Чжоу и др. [5]. В сравнении участвовали два других подхода. Первый подход использовал полный граф на множестве точек в качестве входного для алгоритма Крускала. Второй подход представлял собой реализацию концепции, предложенной в [3]: для каждой точки просканировать все остальные точки, но соединить ее только с ближайшей точкой в каждом квадранте. В эксперименте использовались множества от 1000 до 20000 точек, сгенерированные случайным образом. Результаты эксперимента представлены в таблице 1. В первом столбце указано количество сгенерированных точек; во втором – количество различающихся точек. Для каждого подхода приведены количество ребер в заданном графе и общее время | Экспериментальные результаты построения прямолинейного остовного графа (ПОГ) на основе алгоритма Крускала для вычисления прямолинейного МОД были представлены Чжоу и др. [5]. В сравнении участвовали два других подхода. Первый подход использовал полный граф на множестве точек в качестве входного для алгоритма Крускала. Второй подход представлял собой реализацию концепции, предложенной в [3]: для каждой точки просканировать все остальные точки, но соединить ее только с ближайшей точкой в каждом квадранте. В эксперименте использовались множества от 1000 до 20000 точек, сгенерированные случайным образом. Результаты эксперимента представлены в таблице 1. В первом столбце указано количество сгенерированных точек; во втором – количество различающихся точек. Для каждого подхода приведены количество ребер в заданном графе и общее время выполнения. Если количество точек на входе было больше 10000, подходу на основе полного графа попросту не хватало памяти. | ||
{| class = "wikitable" | {| class = "wikitable" | ||
