11. Структуры данных для геометрического поиска
Алгоритмы и структуры данных, часть 1


Что: Лекция
Когда: Суббота, 16 декабря 2017, 14:30–16:10
Где: НГУ, ауд. 2128
Слайды: algorithms_1_lecture_161217.pdf

Описание

Location problem, stabbing problem. Деревья интервалов. Сведение системы интервалов к двумерной задаче. Задача поиска точек в коридоре. Priority search tree. Задача поиска точек в прямоугольнике. Дерево отрезков по координате X, упорядоченные по Y списки точек в каждой вершине. Сложность O(n log n) для построения и O(log^2 n) для запроса. Уменьшение времени поиска до O(log n). Задача одновременного поиска в наборе упорядоченных списков. Fractional cascading.