Список тем (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 - в котором есть некоторая индексация конспекта)
- Пересечение двух выпуклых многоугольников (лекция 01_1)
- Задача о разделении многоугольника на два равновеликих (лекции 01_3, 02_2)
- Обобщение триангуляции полигонов на случаи с дырками (лекции 02_1-02_2, 03_4) (добавить в триангуляцию - Триангуляция_полигонов_(ушная_+_монотонная))
- Персистентные структуры (лекция 04_*)
- персистентный список за амортизированное O(1)
- персистентные деревья (с ревизиями)
- Локализация точки в многоугольнике (лекция 04_*) (доделать статью - Локализация_в_ППЛГ_методом_полос_(персистентные_деревья))
- Локализация прямоугольника среди прямоугольников (перечислить всех, имеющих с ним хоть одну общую точку) (Большой объем. Все три шага) (лекции 04_*, 05_*, 06_*)
- Fractional Cascading (лекция 05_*) (пример кода) (написать подробно с картинками тут - Перечисление_точек_в_произвольном_прямоугольнике_за_n_*_log_^(d_-_1)_n_(range_tree)#Fractional_cascading)
То, что можно доделать с прошлого года
Возможно есть еще что-то, тут все, что я нашел на скорую руку с этих ссылок:
Неотсортированные темы.
- Пересечение окружностей - можно рассчитать погрешность тут:
Устойчивая реализация алгоритмов вычислительной геометрии.
- Расчет погрешности вычисления предиката (на примере вычисления предиката поворота).
- Дописать ESSA в Интервальную арифметику.
- Интервальная_арифметика
- ESSA: [1]
Выпуклые оболочки на плоскости.
- Алгоритм Джарвиса. (доделать - картинки, возможно пояснения)
- Алгоритм Эндрюса-Грэхема.
- Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
- Выпуклая оболочка как аналог quick sort (без дополнительной памяти).
