City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Поиск на плоскости
Advanced chapters of algorithms, часть 1

What: Lecture
When: Sunday, 19 October 2014, 13:00–14:35
Where: ПОМИ РАН

Description

  1. Ортогональные запросы

    • 1D статическая задача. Массив + бинпоиск.
    • 1D динамическая задача. BST.
    • 2D статическая задача за \(\log^2 n\). 2D дерево.
    • 2D статическая задача за \(\log n\). Бинпоиск + переход по ссылкам.
    • 2D динамическая задача за \(\log^2 n\). Балансировка по весу.
    • Обобщение для больших размерностей. Просто добавь деревьев.
    • 3D статическая задача за \(\log n\). Fractional cascading.
  2. Нахождение многоугольника по точке

    • Offline задача. Сканирующая прямая.
    • Online задача. Персистентное дерево.
    • Сложность по времени и памяти.

Video