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

На базе терминологии, данной в работе [ ], определим свойство единственности следующим образом.

Определение 2. Пусть имеется точка s; область R обладает свойством единственности относительно s, если для каждой пары точек p;q 2 R; ||pq|| < max(||sp||; ||sq||). Разбиение пространства на конечном множество непересекающихся областей обладает свойством единственности относительно s, если каждая из этих областей обладает свойством единственности относительно s.

Нотация ||sp|| используется для представления расстояния между s и p согласно метрике L1. Определим восьмиугольное разбиение плоскости относительно точки s как разбиение, порожденное двумя прямыми линиями под углом 90 градусов и двумя прямыми под углом 45 градусов к ним, как показано на рис. 2a. Здесь каждая из областей, от R1 до R8, включает только одну из ограничивающих ее полупрямых, как можно видеть на рис. 2b. Можно показать, что восьмиугольное разбиение обладает свойством единственности.

Лемма 1. Пусть имеется точка s на плоскости. Восьмиугольное разбиение относительно s обладает свойством единственности.

Доказательство. Чтобы показать, что разбиение обладает свойством единственности, необходимо доказать, что каждая область разбиения обладает этим свойством. Поскольку области R1-R8 аналогичны друг другу, достаточно будет доказать это для области R1.

Точки в области R1 можно охарактеризовать следующими неравенствами

x > xs ; x - y < xs - ys :

Предположим, что имеются точки p и q в R1. Без потери общности будем считать, что xp < xq. Если yp < yq, то

||sq|| = ||sp|| + ||pq|| > ||pq||. Следовательно, необходимо рассмотреть только случай yp > yq. В данном случае

||pq|| = \xp-xq\ + \yp- yqj = xq-xp + yp-yq = (xq - yq) + yp - xp < (xs - ys) + yp – xs = yP-ys <xp-xs + yp-ys

Пусть даны две точки p, q в одном и том же сегменте (октанте) восьмиугольного разбиения плоскости относительно точки s. Согласно свойству единственности, ||pq|| < max(||sp||; ||sq||). Рассмотрим цикл с точками s, p и q. Согласно свойству циклов, только одну точку с минимальным расстоянием до s необходимо соединить с s. Интересное свойство восьмиугольного разбиения заключается в том, что контур равноудаленных от s точек формирует отрезок прямой в каждой области. В областях R1, R2, R5, R6 эти сегменты описываются уравнением вида x + y = c; в областях R3, R4, R7, R8 – уравнением вида x - y = c.

Для каждой точки s необходимо найти ближайшего к ней соседа в каждом октанте. Опишем, как эффективно вычислить соседей в октанте R1 для всех точек. Случаи остальных октантов симметричны. Для октанта R1 алгоритм с заметающей прямой исполняется для всех точек в порядке неубывания x + y. В процессе заметания поддерживается активное множество, состоящее из точек, для которых ближайшие соседи в R1 еще не найдены. После обработки точки p будут найдены все точки активного множества, содержащие p в их областях R1. Если такая точка содержится в активном множестве, то, поскольку точки проверяются в порядке неубывания x + y, p должна быть ближайшей точкой для s в R1.  

Фундаментальной операцией алгоритма с заметающей прямой является нахождение подмножества активных точек, такого, что заданная точка p принадлежит к их областям R1. Основываясь на наблюдении, что точка p принадлежит к области R1 точки s в том и только том случае, если s принадлежит к области R5 точки p, необходимо найти подмножество активных точек в области R5 точки p. Поскольку область R5 может быть представлена как двумерный диапазон (00,xp] x (xp - yp;+1) на (x, x - y), для поддержки множества активных точек можно использовать дерево поиска с приоритетами [ ]. Поскольку каждая операция вставки и удаления требует O(log n) времени, а операция запроса – O(log n+ k) времени, где k – количество объектов в диапазоне, общее время работы алгоритма с заметающей прямой составит O(nlogn). Другие области могут быть обработаны аналогично R1, так что полное время работы алгоритма составит O(n log n). Дерево поиска с приоритетами – это структура данных, поддерживающая сбалансированность ради быстрого осуществления поиска. Она отлично работает для статических входных множеств. Если входное множество оказывается динамическим, перебалансировка дерева может представлять серьезную проблему. К счастью, активное множество имеет структуру, которая допускает альтернативное представление. Поскольку точка удаляется из активного множества, если найдена точка в ее области R1, никакая точка активного множества не может принадлежать к области R1 другой точки множества.

Чтобы найти подмножество активных точек, для которых s находится в их областях R1, вначале необходимо найти наибольшее x, такое, что x < xs, а затем выполнять обработку в порядке убывания x, до тех пор, пока x - y > xs - ys. Поскольку упорядочение производится только по одному измерению, использование любого бинарного дерева поиска со стоимостью операций вставки, деления и запроса, равной O(log n), получаем алгоритм с временем исполнения O(n log n). Бинарные деревья запроса также требуют балансировки. Кроме того, можно использовать списки с пропусками [ ], использующие рандомизацию во избежание проблемы явной балансировки, но демонстрирующие ожидаемое поведение на уровне O(log n).

Внимательное рассмотрение также позволяет прийти к выводу, что после заметания области R1 нет необходимости в заметании R5, поскольку все ребра, необходимые на данном этапе, уже подключены или предполагаются. Более того, основываясь на информации из R5, количество реберных соединений можно еще больше сократить. Во время обработки заметающим процессом точки s он находит подмножество активных точек, содержащих s в их областях R1. Без потери общности будем считать, что к ним относятся точки p и q. Тогда p и q принадлежат к области R5 точки s, что означает ||pq|| < max(||sp||; ||sq||). Следовательно, необходимо только соединить s с ближайшей активной точкой.

R1 и R2 имеют одну и ту же последовательность заметания и в силу этого могут быть обработаны вместе за один проход алгоритма. Аналогично области R3 и R4 могут быть обработаны вместе за второй проход. На основе вышеприведенных рассуждений составим псевдокод алгоритма, представленный на рис. 2.

За время работы алгоритма каждая точка будет добавлена в активное множество и удалена из него только один раз для каждой из областей R1-R4. Каждая операция вставки и удаления требует O(log n) времени. Таким образом, верхняя граница временной сложности алгоритма O(n log n). Хранить необходимо только активные множества, так тчо объем памяти для хранения не превышает O(n). □