Описание: Основные понятия вычислительной геометрии. Мера сложности вычислений. Асимптотический анализ сложности. Рекурсивные алгоритмы. Оценка вычислительной сложности задачи.
Алгоритмическая парадигма «разделяй и властвуй». Геометрический поиск. Локализация точки в простом и в выпуклом многоугольнике при уникальном и массовом запросе. Локализация точки в планарном подразбиении.
Построение выпуклых оболочек. Алгоритмы Джарвиса, Грэхема. Слияние выпуклых оболочек. Метод редукции для оценки сложности задачи.
Пересечения геометрических объектов. Пересечения конечного множества отрезков. Алгоритмическая парадигма плоского заметания. Структуры данных в алгоритме заметания.
Близость геометрических объектов. Разбиения Вороного и триангуляции Делоне. Преобразования двойственных графов. Алгоритмы построения триангуляции Делоне: наивные, жадные, инкрементные, флип-флоп, рекурсивные. Обобщенные диаграммы Вороного для различных множеств сайтов – кругов, отрезков, многоугольников.
Обобщенная диаграмма Вороного и скелет многоугольной фигуры.