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

798

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

  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.