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

Осенний семестр

• Кратчайший путь O(n^2). Overmars and Welzl’s Algorithm & rotation tree. Visibility_graph_и_motion_planning#Overmars_and_Welzl.E2.80.99s_Algorithm

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

Материалы можно найти в 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)

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

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

• Вычислительная_геометрия
• Список_тем

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

• Пересечение окружностей - можно рассчитать погрешность тут:

  Пересечение_окружностей

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

• Расчет погрешности вычисления предиката (на примере вычисления предиката поворота).

  презентация в csклубе

• Дописать ESSA в Интервальную арифметику.

  Интервальная_арифметика

  ESSA: [1]

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

Я упустил, эти алгоритмы описаны здесь: Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull

• Алгоритм Джарвиса. (доделать - картинки, возможно пояснения)

  Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости

  [2]

• Алгоритм Эндрюса-Грэхема.

  Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости

  [3]

• Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).

  Дописать сюда: Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull

  этот вроде как раз подойдет

• Выпуклая оболочка как аналог quick sort (без дополнительной памяти).

  Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости

  [4]