К.В. Вяткина

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

Данный курс задуман как продолжение курса «Основы вычислительной геометрии», прочитанного в осеннем семестре 2009г. Ожидается, что слушатели будут иметь достаточно четкое представление о вопросах, обсуждавшихся в его рамках. (В то же время, желающим могут быть предоставлены материалы для самостоятельного ознакомления с базовыми методами вычислительной геометрии; возможно также проведение небольшого «ликбеза» по согласованию с заинтересованными слушателями.)

Основные темы второй части курса

• Ортогональный региональный поиск (orthogonal range search): kd-деревья, деревья регионов (range trees), частичное каскадирование (fractional cascading).
• Линейное программирование: детерминированный и вероятностный алгоритмы.
• Выпуклая оболочка (ВО) множества точек в трехмерном пространстве: структуры данных для представления многогранников; детерминированные алгоритмы построения ВО; вероятностный алгоритм построения ВО; связь с задачей нахождения пересечения полупространств.
• Планирование движения робота (robot motion planning): рабочее и конфигурационное пространства; случай точечного робота; суммы Минковского; случай полигонального робота.
• Геометрические структуры данных: дерево интервалов, дерево поиска с приоритетом (priority search tree), дерево отрезков.
• BSP-дерево: определение, применение, построение, размер.
• Квадродеревья (quadtrees): задача генерации сетки; квадродерево для множества точек на плоскости и его использование для генерации сетки.
• Симплициальный региональный поиск (simplex range search): деревья разбиения (partition trees), многоуровневые деревья разбиения (multi-level partition trees), деревья разрезов (cutting trees).

Литература

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, Cambridge University Press, 1998.
4. Ф. Препарата, М. Шеймос, “Вычислительная геометрия: введение”, пер. с англ., М., Мир, 1989.