К.В. Вяткина, "Вычислительная геометрия - II"

К.В. Вяткина, "Вычислительная геометрия - II"

К.В. Вяткина

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

Начало 13.02.10 в

10:00 ауд 311 ПОМИ

Данный курс задуман как продолжение курса «Основы вычислительной геометрии», прочитанного в осеннем семестре 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).

Литература

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