Список тем

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

• Как устроены числа с плавающей точкой?

  Представление_вещественных_чисел

  Представление_чисел_с_плавающей_точкой

• Расчет погрешности вычисления предиката (на примере вычисления предиката поворота). Обратите внимание, что готовить эту тему следует по моей видеолекции, там я расписал вычисление погрешности гораздо аккуратнее.

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

• Интервальная арифметика. Длинная арифметика. ESSA.

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

TODO: по ESSA вообще ничего не нашел

• Adaptive precision арифметика.

  Adaptive_precision_arithmetic

  статья Шевчука

Конфигурации пространства. Определение и построение.

• Предикат пересечения отрезков.

  Предикат_"левый_поворот"

• Пересечение множества отрезков (Bentley-Ottmann).

  Алгоритм_Бентли-Оттмана

• Представление конфигураций плоскости (DCEL). Конфигурация множества прямых на плоскости. Конфигурация множества отрезков на плоскости.

  Конфигурация

Конфигурации пространства. Локализация.

• Локализация в выпуклом многоугольнике. Локализация в многоугольнике общего вида. Геометрический хеш.

  Wikipedia — Geometric hashing — на лекции не был, посмотрите, мало ли это не то.

• Алгоритм Киркпатрика.

  Википедия — Алгорити Киркпатика — что это делает здесь, казалось бы, это надо в выпуклые оболочки.

• Трапецоидная карта.
• Инкрементальная локализация на дереве отрезков.
• Метод полос.

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

• Алгоритм Джарвиса.
• Алгоритм Эндрюса-Грэма.
• Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
• Выпуклая оболочка как аналог quick sort (без дополнительной памяти).

Типовые задачи

• Расписать погрешность предиката (например, поворот отрезка и точки пересечения двух отрезков).
• Пересечение множества окружностей разного радиуса.
• Выпуклая оболочка множества окружностей одинакового радиуса.
• Выпуклая оболочка множества окружностей разного радиуса.