12
правок
Изменения
Нет описания правки
* Пересечение двух выпуклых многоугольников (лекция 01_1)
* Задача о разделении многоугольника на два равновеликих (лекции 01_3, 02_2)
* Обобщение триангуляции полигонов на случаи с дырками (лекции 02_1-02_2, 03_4) (добавить в триангуляцию - [[Триангуляция_полигонов_(ушная_%2B_монотонная)]])
* Персистентные структуры (лекция 04_*)
*: персистентный список за амортизированное O(1)
*: персистентные деревья (с ревизиями)
* Локализация точки в многоугольнике (лекция 04_*) (доделать статью - [[Локализация_в_ППЛГ_методом_полос_(персистентные_деревья)]])* Локализация прямоугольника среди прямоугольников (перечислить всех, имеющих с ним хоть одну общую точку) (Большой объем. Все три шага) (лекции 04_*, 05_*, 06_*)* Fractional Cascading (лекция 05_*) ([https://github.com/PolarHare/Fractional-Cascading/blob/master/src/Problem16E.java пример кода]) (написать подробно с картинками тут - [[Перечисление_точек_в_произвольном_прямоугольнике_за_n_*_log_%5E(d_-_1)_n_(range_tree)#Fractional_cascading]])
==То, что можно доделать с прошлого года==
