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

Лектор: Вяткина К.В., доц. каф. системного программирования мат.-мех. ф-та СПбГУ и каф. математического моделирования ЕНФ СПбГУ ИТМО

продолжение в весеннем семестре 12 февраля в 10:00

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

Первый семестр

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

VIII.Видимость и кратчайшие пути: 2 ч.

Кратчайшие пути на плоскости при наличии полигональных препятствий. Приближенный метод построения кратчайшего пути с использованием трапецоидальной карты. Понятие графа видимости (visibilitygraph). Нахождение кратчайших путей с использованием графа видимости. Построение графа видимости. Возможные обобщения понятия видимости.

Второй семестр

IX.Ортогональный региональный поиск: 4 ч.

Ортогональные региональные запросы (orthogonalrangequeries). Задача одномерного регионального поиска. Kd-деревья: определение, размер, построение, использование для обработки запросов на плоскости; обобщение на случай d-мерного пространства. Деревья регионов (rangetrees): определение, размер, построение, использование для обработки запросов на плоскости; обобщение на случай d-мерного пространства. Частичное каскадирование (fractionalcascading) и его применение для ускорения обработки запросов с использованием дерева регионов.

X.Линейное программирование: 4 ч.

Пересечение полуплоскостей: алгоритм «разделяй и властвуй». Решение двумерной задачи линейного программирования: детерминированный (инкрементный) и вероятностный алгоритмы. Обобщение на случай пространств высшей размерности.

XI.Выпуклые оболочки в трехмерном пространстве: 4 ч.

Выпуклая оболочка (ВО) множества точек в трехмерном пространстве: определение и комбинаторная сложность. Структуры данных для представления многогранников. Детерминированные алгоритмы и вероятностный алгоритм построения ВО множества точек в трехмерном пространстве. Связь с задачей нахождения пересечения полупространств.

XII.Планирование движения: 4 ч.

Задача планирования движения робота (robotmotionplanning) на плоскости при наличии полигональных препятствий. Рабочее и конфигурационное пространства. Случай точечного робота. Суммы Минковского: определение и использование для нахождения препятствий в конфигурационном пространстве. Оптимальный алгоритм построения суммы Минковского двух выпуклых многоугольников на плоскости. Случай полигонального робота.

XIII.Дополнительные геометрические структуры данных: 16 ч.

Оконные запросы (windowingqueries). Дерево интервалов (intervaltree): определение, размер,построение, использование для обработки одномерных запросов о прокалывании (stabbingqueries) и двумерных оконных запросов для множества отрезков, параллельных осям координат. Дерево поиска с приоритетом (prioritysearchtree): определение, размер, построение, использование для обработки двумерных неограниченных ортогональных региональных запросов. Дерево отрезков (segmenttree): определение, размер, построение, использование для обработки одномерных запросов о прокалывании и двумерных оконных запросов для множества попарно непересекающихся отрезков.

BSP-дерево: определение, применение, построение, размер.

Задача генерации сетки (meshgeneration). Квадродерево (quadtree) для множества точек на плоскости и его использование для генерации сетки.

Симплициальный региональный поиск (simplexrangesearch). Дерево разбиения (partitiontree): определение, размер, построение, использование для обработки двумерных запросов симплициального регионального поиска. Многоуровневое дерево разбиения (multi-levelpartitiontree): определение, размер, построение и применение. Дерево разрезов (cuttingtree): определение, размер, построение, использование для обработки двумерных запросов симплициального регионального поиска.

Литература

1. M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, “Computational Geometry: Algorithms and Applications”, Third Edition, Springer, Heidelberg, 2008.
2. J-D. Boissonnat and M. Yvinec, “Géométrie algorithmique”. Ediscience international, Paris, 1995.
3. J. O’Rourke, “Computational Geometry in C”, Second Edition, CambridgeUniversity Press, 1998.
4. Ф. Препарата, М. Шеймос, “Вычислительная геометрия: введение”, пер. с англ., М., Мир, 1989.