Курс лекций "Основы вычислительной геометрии" (1 семестр, 28 часов)

К.В. Вяткина, СПбГУ и СПбГУ ИТМО

Аннотация. Курс посвящен основным алгоритмам вычислительной геометрии, используемым в самых разных приложениях геометрии, в т.ч. computervision, геоинформатика, биоинформатика, стереовидение и т.п.

I. Введение: 2 ч.

Предмет вычислительной геометрии. Используемая модель вычислений. Индивидуальные и массовые запросы. Сложность алгоритма: время ответа на запрос, затраты памяти, время на предварительную обработку. Многоугольники: простые, выпуклые, звездные. Ядро звездного многоугольника. Задача о принадлежности точки простому, выпуклому, звездному многоугольнику.

II. Выпуклые оболочки: 4 ч.

Определение выпуклой оболочки (ВО) множества точек на плоскости. Нижняя оценка сложности ее построения. Наивный алгоритм построения ВО множества точек на плоскости. Понятие общего положения. Вырожденные случаи. Понятие устойчивости алгоритма (robustness). Модифицированный метод Грэхема. Нижняя оценка сложности построения ВО множества точек на плоскости. Другие алгоритмы построения ВО множества точек на плоскости: метод обхода Грэхема; метод заворачивания подарка (метод Джарвиса) - алгоритм, чувствительный к выходу (output sensitive); инкрементный алгоритм; метод <<разделяй и властвуй>> (с предварительной сортировкой точек и без нее); <<быстрая оболочка>>; алгоритм Чена. Выбор наиболее подходящего алгоритма с учетом конкретной ситуации.

III. Пересечение отрезков и наложение планарных подразбиений: 4 ч.

Задача о нахождении всех пересечений отрезков из заданного множества. Нижняя оценка сложности: проверка наличия двух пересекающихся отрезков в заданном множестве. Нахождение пересечений отрезков методом плоского заметания. Реберный список с двойными связями (РСДС). Плоский прямолинейный граф (ППЛГ). Планарное подразбиение. Задача наложения (overlay) планарных подразбиений и алгоритм ее решения. Частные случаи: пересечение выпуклых многоугольников; пересечение простых многоугольников.

IV. Триангуляция многоугольника: 4 ч.

Диагональ простого многоугольника: определение и лемма о существовании. Триангуляция простого многоугольника: определение, лемма о существовании, сложность (количество треугольников в триангуляции). Наивный алгоритм построения триангуляции простого многоугольника. Граф, двойственный триангуляции: определение и свойства. Построение триангуляции простого многоугольника путем <<отрезания ушей>>. 3-раскрашиваемость графа триангуляции простого многоугольника. Задача о картинной галерее. Монотонные многоугольники. Разбиение простого многоугольника на y-монотонные. Построение триангуляции монотонного многоугольника. Триангуляция произвольных многоугольников и ППЛГ.

V. Локализация точки на планарном подразбиении: 4 ч.

Постановка задачи. Метод полос и оценка его сложности. Метод детализации триангуляции Киркпатрика и оценка его сложности. Трапецоидальная карта (trapezoidal map): определение, сложность, представление. Вероятностный алгоритм построения трапецоидальной карты. Оценка ожидаемого времени построения трапецоидальной карты, ожидаемого размера поисковой структуры данных (search structure) и ожидаемого времени обработки запроса на локализацию точки.

VI. Диаграмма Вороного и триангуляция Делоне: 6 ч.

Определение и основные свойства диаграммы Вороного множества точек на плоскости. Наивный алгоритм построения диаграммы Вороного. Нижняя оценка сложности построения диаграммы Вороного. Оптимальные алгоритмы построения диаграммы Вороного: метод плоского заметания, метод <<разделяй и властвуй>>. Возможности обобщения понятия диаграммы Вороного.

Определение и свойства триангуляций множества точек на плоскости. Легальные (legal) триангуляции: определение и построение. Граф Делоне и его свойства. Триангуляция Делоне. Вероятностный алгоритм построения триангуляции Делоне и анализ его сложности.

VII. Конфигурации прямых на плоскости и двойственность: 4 ч.

Задача о вычислении расхождения (discrepancy). Двойственность точек и прямых. Конфигурации (arrangements) прямых на плоскости: определение, сложность, инкрементный алгоритм построения. Понятие зоны прямой в конфигурации; теорема о зоне (Zone Theorem). Оценка сложности инкрементного алгоритма построения конфигурации. Понятие уровня (level) точки в конфигурации прямых. Вычисление уровней вершин конфигурации и их связь с величиной расхождения.