Алгоритмы и структуры данных поиска: Задачи геометрического поиска. Бабенко Максим

Бабенко Максим рассказывает о задачах геометрического поиска.

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