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

Нотация ||sp|| используется для представления расстояния между s и p согласно метрике <math>L_1 \;</math>. Определим ''восьмиугольное разбиение'' плоскости относительно точки s как разбиение, порожденное двумя прямыми линиями под углом 90 градусов и двумя прямыми под углом 45 градусов к ним, как показано на рис. 1(а). Здесь каждая из областей, от <math>R_1 \;</math> до <math>R_8 \;</math>, включает только одну из ограничивающих ее полупрямых, как можно видеть на рис. 1(б). Можно показать, что восьмиугольное разбиение обладает свойством единственности.

Фундаментальной операцией алгоритма с заметающей прямой является нахождение подмножества активных точек, такого, что заданная точка p принадлежит к их областям <math>R_1 \;</math>. Основываясь на наблюдении, что точка p принадлежит к области <math>R_1 \;</math> точки s в том и только том случае, если s принадлежит к области <math>R_5 \;</math> точки p, необходимо найти подмножество активных точек в области <math>R_5 \;</math> точки p. Поскольку область <math>R_5 \;</math> может быть представлена как двумерный диапазон <math>( - \infty ,x_p ] \times (x_p - y_p, + \infty) \;</math> на <math>(x, x - y) \;</math>, для поддержки множества активных точек можно использовать дерево поиска с приоритетами [1]. Поскольку каждая операция вставки и удаления требует O(log n) времени, а операция запроса – O(log n+ k) времени, где k – количество объектов в диапазоне, общее время работы алгоритма с заметающей прямой составит O(nlogn). Другие области могут быть обработаны аналогично <math>R_1 \;</math>, так что полное время работы алгоритма составит O(n log n). Дерево поиска с приоритетами – это структура данных, поддерживающая сбалансированность ради быстрого осуществления поиска. Она отлично работает для статических входных множеств. Если входное множество оказывается динамическим, перебалансировка дерева может представлять серьезную проблему. К счастью, активное множество имеет структуру, которая допускает альтернативное представление. Поскольку точка удаляется из активного множества, если найдена точка в ее области <math>R_1 \;</math>, никакая точка активного множества не может принадлежать к области <math>R_1 \;</math> другой точки множества.

'''Лемма 2. Для любых двух точек p, q в активном множестве должно выполняться <math>x_p \ne x_q \;</math>, и если <math>x_p < x_q \;</math>, то <math>x_p - y_p \le x_q - y_q \;</math>.'''

Основываясь на этом свойстве, можно упорядочить активное множество в соответствии с возрастанием x. Из этого следует неубывающий порядок x - y. Пусть дана точка s; точки, для которых s находится в их областях <math>R_1 \;</math>, должны удовлетворять следующим неравенствам: <math>x \le x_s; x - y > x_s - y_s \;</math>.