Список тем

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

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

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

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

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

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

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

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

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

- пожалуйста: [1]

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

  Adaptive_precision_arithmetic

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

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

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

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

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

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

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

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

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

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

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

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

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

• Трапецоидная карта.

  [2]

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

• Может, тут все-таки имелось в виду дерево интервалов?

• Метод полос.

  Wikipedia — Point location

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

• Алгоритм Джарвиса.

  [3]

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

  [4]

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

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

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

  [5]

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

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