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

Фундаментальной операцией алгоритма с заметающей прямой является нахождение подмножества активных точек, такого, что заданная точка 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> другой точки множества.