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

• Представление чисел с плавающей точкой
• Предикат "левый поворот"
• Интервальная арифметика
• Adaptive precision arithmetic
• Алгоритм Бентли-Оттмана
• Конфигурация
• Трапецоидная карта
• Алгоритм Киркпатрика детализации триангуляции
• Пересечение окружностей
• Упрощение полигональной цепи
• Ортогональный поиск
• Алгоритмы построения выпуклых оболочек множества точек на плоскости
• Триангуляция полигонов (ушная + монотонная)

---

• Список тем
• Сдача конспектов
• Сдача презентаций
• Условия и чекеры

---

• Туториал по cmake
• Тестирование с использованием Google Test

Базовые алгоритмы и структуры данных

• Skip quadtree: определение, время работы
• Квадродеревья и перечисление точек в произвольном прямоугольнике (статика)
• Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)
• Дерево интервалов (interval tree) и пересечение точки с множеством интервалов
• Пересечение прямоугольника с множеством прямоугольников (PST)

Аффинное пространство

• Пересечение отрезков и поворот: определение, свойства, вычисление
• Принадлежность точки выпуклому и невыпуклому многоугольникам
• Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)
• Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull
• Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление)
• Выпуклая оболочка в n-мерном пространстве
• Триангуляция многоугольника за n^2
• Триангуляция многоугольника заметающей прямой
• Пересечение полуплоскостей, связь с выпуклыми оболочками
• Пересечение множества отрезков
• Snap rounding
• ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых
• Пересечение многоугольников (PSLG overlaying)
• Локализация в ППЛГ методом полос (персистентные деревья)
• Локализация в ППЛГ. Алгоритм Киркпатрика
• Трапецоидная карта

Скалярное произведение и мера

• Диаметр множества точек (вращающиеся калиперы)
• Сумма Минковского (определение, вычисление)
• Минимальная охватывающая окружность множества точек
• Visibility graph и motion planning
• Триангуляция Делоне
• Диаграмма Вороного
• straight skeleton
• WRP + continuous Dijkstra (специально для Сени и Юрика :)