Список тем (year 2012) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
* Пересечение двух выпуклых многоугольников (лекция 01_1)
 
* Пересечение двух выпуклых многоугольников (лекция 01_1)
 
* Задача о разделении многоугольника на два равновеликих (лекции 01_3, 02_2)
 
* Задача о разделении многоугольника на два равновеликих (лекции 01_3, 02_2)
* Обобщение триангуляции полигонов на случаи с дырками (лекции 02_1-02_2, 03_4) (добавить в триангуляцию - [Триангуляция_полигонов_(ушная_%2B_монотонная)])
+
* Обобщение триангуляции полигонов на случаи с дырками (лекции 02_1-02_2, 03_4) (добавить в триангуляцию - [[Триангуляция_полигонов_(ушная_%2B_монотонная)]])
 
* Персистентные структуры (лекция 04_*)
 
* Персистентные структуры (лекция 04_*)
 
*: персистентный список за амортизированное O(1)
 
*: персистентный список за амортизированное O(1)
 
*: персистентные деревья (с ревизиями)
 
*: персистентные деревья (с ревизиями)
* Локализация точки в многоугольнике (лекция 04_*) (доделать статью - [Локализация_в_ППЛГ_методом_полос_(персистентные_деревья)])
+
* Локализация точки в многоугольнике (лекция 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]])
  
 
==То, что можно доделать с прошлого года==
 
==То, что можно доделать с прошлого года==

Версия 15:15, 5 июля 2014

Пройденное за весенний семестр

Материалы можно найти в dropbox (там есть README - в котором есть некоторая индексация конспекта)

То, что можно доделать с прошлого года

Возможно есть еще что-то, тут все, что я нашел на скорую руку с этих ссылок:

Неотсортированные темы.

Устойчивая реализация алгоритмов вычислительной геометрии.

Выпуклые оболочки на плоскости.