City:
Saint Petersburg
Novosibirsk
Kazan
Language:
Русский
English
About CS Club
Courses
Lecturers
Schools
Login
Registration
Поиск на плоскости
Advanced chapters of algorithms, part 1
What:
Lecture
When:
Sunday, 19 October 2014, 13:00–14:35
Where:
ПОМИ РАН
Description
Ортогональные запросы
1D статическая задача. Массив + бинпоиск.
1D динамическая задача. BST.
2D статическая задача за \(\log^2 n\). 2D дерево.
2D статическая задача за \(\log n\). Бинпоиск + переход по ссылкам.
2D динамическая задача за \(\log^2 n\). Балансировка по весу.
Обобщение для больших размерностей. Просто добавь деревьев.
3D статическая задача за \(\log n\). Fractional cascading.
Нахождение многоугольника по точке
Offline задача. Сканирующая прямая.
Online задача. Персистентное дерево.
Сложность по времени и памяти.
Video