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


Что: Семинар
Когда: Суббота, 08 декабря 2018, 14:30–16:05
Где: НГУ, ауд. 2128
Слайды: algorithms_1_seminar_081218.pdf

Описание

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

Видео