Что: Лекция
Когда: Воскресенье, 19 октября 2014, 13:00–14:35
Где: ПОМИ РАН

Описание

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

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

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

Видео