Список тем (year 2012)

2014-07-07T04:54:22Z

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

==Пройденное за весенний семестр==
Материалы можно найти в [https://www.dropbox.com/sh/i8ka1e4dr7girdh/AABgCA2Y8RYym90xJNO_m7Wka dropbox] (там есть README - в котором есть некоторая индексация конспекта)

* [[Пересечение_отрезков_на_сфере]] (доделать)
* Пересечение двух выпуклых многоугольников (лекция 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]])

==То, что можно доделать с прошлого года==
Возможно есть еще что-то, тут все, что я нашел на скорую руку с этих ссылок:
* [[Вычислительная_геометрия]]
* [[Список_тем]]

===Неотсортированные темы.===
* Пересечение окружностей - можно рассчитать погрешность тут:
*: [[Пересечение_окружностей]]

===Устойчивая реализация алгоритмов вычислительной геометрии.===
* Расчет погрешности вычисления предиката (на примере вычисления предиката поворота).
*: [http://compsciclub.ru/node/1563 презентация в csклубе]
* Дописать ESSA в Интервальную арифметику.
*: [[Интервальная_арифметика]]
*: ESSA: [http://pages.cpsc.ucalgary.ca/~marina/papers/Segment_intersection.ps]

=== Выпуклые оболочки на плоскости. ===
Я упустил, эти алгоритмы описаны здесь: [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull]]
* <del>Алгоритм Джарвиса. (доделать - картинки, возможно пояснения)</del>
*: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]]
*: [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%B0%D1%80%D0%B2%D0%B8%D1%81%D0%B0]
* <del>Алгоритм Эндрюса-Грэхема.</del>
*: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]]
*: [http://nms.lcs.mit.edu/~aklmiu/6.838/convexhull/]
* Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
*: Дописать сюда: [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull]]
*: [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B8%D1%80%D0%BA%D0%BF%D0%B0%D1%82%D1%80%D0%B8%D0%BA%D0%B0 этот вроде как раз подойдет]
* <del>Выпуклая оболочка как аналог quick sort (без дополнительной памяти).</del>
*: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]]
*: [http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/QuickHull.html]

[[Категория: Вычислительная геометрия]]

Викиконспекты - Вклад участника [ru]

Список тем (year 2012)