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

Вводная лекция

Обзор курса. Несколько слов об аналитической геометрии (напоминание, что существуют не только декартовы координаты).

- Гомогенные координаты, бесконечно удаленные точки.
- Пересечение прямой и окружности (использование векторной записи).
- Центр вписанной и описанной окуржности треугольника (использование барицентрицеских координат).
- Проверка принадлежности точки описанному около треугольника кругу (параболоид z = x^2 + y^2).

Знакомство с полигоном и его триангуляцией
- Определение и естественные свойства полигона.
- Art Gallery Problem.
- Определение триангуляции полигона, объяснение откуда взялся корень “трианг”.
- Двойственный граф триангуляции. Существование у полигона ушей.

Площадь полигона. Алгоритмы триангуляции полигона
- Вычисление площади полигона (формула, наглядное представление).
- Отрезание ушей.
- Определение монотонной цепи, монотонного полигона, триангуляция монотонного полигона.
- Заметающая прямая, алгоритм разбиения полигона на монотонные.

ППЛГ, формула Эйлера
- Определение полигона с дырками.
- Определение ППЛГ.
- РСДС – способ хранить ППЛГ, подходящий для алгоритма разбиения полигона на монотонные.
- Формула Эйлера для ППЛГ – важнейший инструмент доказательства оценок в вычислительной геометрии на плоскости.

Выпуклая оболочка множества точек (есть конспект)
- Естественное определение, конструктивное определение.
- Нижняя оценка времени работы алгоритма построения.
- Алгоритмы построения.

Триангуляция множества точек
- Определение, объяснение откуда взялся корень “трианг”.
- Подсчет количества треугольников в произвольной триангуляции.
- Простой алгоритм построения за O(n log n).
- Определение триангуляции Делоне.
- Доказательство существования триангуляции Делоне.
- Некоторые свойства триангуляции Делоне, объясняющие, почему ей все вокруг восторгаются.

Локализация в триангуляции
- Метод детализации триангуляции Кирпатрика.
- Инкрементальный алгоритм построения триангуляции Делоне.

Диаграмма Вороного
- Определение, некоторые свойства.
- Определение двойственного графа – графа Делоне. Связь с триангуляцией Делоне.
- Алгоритм построения Форчуна (заметающая прямая). Объяснение, почему на практике им пользоваться не стоит.
- Мимимальное остовное дерево и задача коммивояжера на плоскости.

Задачи регионального поиска (в множестве точек)
- kd-tree (k == 2).
- Range Tree. Эвристика, позволяющая сократить время обработки запроса до O(log n).

Задачи регионального поиска (в множестве отрезков)
- Interval Tree. Priority Search Tree.
- Segment Tree: построение за O(n log n).

Локализация в произвольном ППЛГ
- Локализация точки в простом полигоне, полигоне с дырками, системе полигонов.
- Трапецоидальная карта.

Пересечение множества отрезков
- Алгоритм Бентли-Отмана.
- Snap rounding.

Клиповка полигонов
- Пересечение, объединение, разность, симметрическая разность множества полигонов с дырками.
- Пересечение множества полуплоскостей (сведение к выпуклой оболочке в двойственном пространстве).
- Пересечение выпуклых полигонов (сведение к объединению выпуклых оболочек).

Поиск пути на плоскости для точечного робота
- Формулировка задачи в случае полигональных препятствий.
- Roadmap.
- Форма кратчайшего пути.
- Visibility graph. Rotational plane sweep.
- Полилинейные препятствия, Reduced visibility graph.
- Поиск кратчайшего пути в простом полигоне. Доказательство единственности, funnel algorithm.

Поиск пути на плоскости для полигонального робота
- Configuration space, free space, forbidden space.
- Сумма Минковского, вычисление суммы минковского выпуклых полигонов за O(n).
- Сведение задачи для невращающегося полигонального робота к задаче для точечного робота за O(n log^2 n).

Преподаватель:
Андрей Давыдов