Тематический план
Введение
Предмет дисциплины и ее задачи. Исторический обзор. Содержание и форма проведения занятий. Связь с другими дисциплинами учебного плана.Тема 1. Модели вычислений и сложность алгоритмов
Модели вычислений и абстрактные машины. Метод преобразования задач. Нижние и верхние оценки сложности. Деревья решений и нижние оценки сложности.Тема 2. Специальные структуры данных в комбинаторных геометрических задачах
Структуры данных для работы с множествами: словарь, приоритетная очередь, сливаемая пирамида, сцепляемая очередь. Реализация сцепляемых очередей на базе АВЛ-деревьев. Рандомизированные двоичные деревья поиска и реализация на их основе сцепляемых очередей. Деревья отрезков. Определение, назначение, свойства, построение, операции. Представление планарных графов реберным списком с двойными связями (РСДС). Обход ребер, инцидентных вершине. Обход ребер вокруг грани.Тема 3. Основные алгоритмы
Рандомизированный алгоритм построения выпуклой оболочки. Построение выпуклой оболочки в реальное время. Построение выпуклой оболочки в трехмерном пространстве.Тема 4. Расширения и приложения
Алгоритмы аппроксимации выпуклой оболочки. Охватывающая оболочка. Оценка приближения. Выпуклая оболочка простого многоугольника. Алгоритм Ли. Задача о глубине множества и ее решение. Задача о диаметре множества точек. Нижняя оценка (связь с задачей о разделимости множеств). Противолежащие пары. Оптимальный алгоритм нахождения диаметра множества.Тема 5. Введение в геометрический поиск
Виды поиска. Массовый и уникальный поиск. Задача локализации. Задача регионального поиска. Меры оценки алгоритмов поиска: время запроса, память, время предобработки, время корректировки. Пример решения задачи регионального поиска (подсчета) – метод локусов.Тема 6. Задачи локализации точки
Принадлежность многоугольнику. Метод луча. Выпуклый многоугольник. Звездный многоугольник. Локализация точки на планарном подразбиении. Метод полос. Предобработка: алгоритм плоского заметания. Локализация. Метод цепей. Монотонные цепи. Полное множество монотонных цепей графа. Регулярный граф и построение полного множества его монотонных цепей. Регуляризация графа. Локализация в множестве монотонных цепей. Метод детализации триангуляции. Предобработка. Локализация. Анализ сложности. Метод трапеций (рекурсивный алгоритм). Метод трапеций Сайделя (пошаговый алгоритм).Тема 7. Задачи регионального поиска
Метод сетки. Метод квадрантного дерева. Построение адаптивного квадрантного дерева. Процедура поиска. Анализ в худшем случае и в среднем. Метод 2-D дерева. Построение дерева. Поиск. Анализ худшего случая. Региональный поиск. Метод прямого доступа. Двухэтапная схема. Дерево отрезков. Метод дерева регионов в задаче регионального поиска.Тема 8. Набор и решение задач о близости
Набор задач о близости (Ближайшая пара, Все ближайшие соседи, Евклидово минимальное остовное дерево - ЕМОД, Триангуляция, Поиск ближайшего соседа). Задача единственности элементов как вычислительный прототип. Нижняя граница сложности. Нижние оценки сложности задач о близости. Задача о ближайшей паре. Метод сбалансированного разделения и слияния. Диаграмма Вороного. Определение, свойства. Триангуляция Делоне. Построение диаграммы Вороного. Алгоритм сбалансированного разделения и слияния Шеймоса и Хоуи (Shaimos & Hoey). Разделяющая цепь. Построение разделяющей цепи. Построение диаграммы Вороного. Алгоритм с заметанием (Fortune). Нижняя оценка для построения диаграммы Вороного. Решение задач о близости с помощью диаграммы Вороного. Решение задачи о Евклидовом МОД.