City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Computational Geometry
Saint Petersburg / spring 2014, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

Список литературы:

  • M. de Berg, O. Cheong, M. van Kreveld, M.Overmars, Computational Geometry: Algorithms and Applications, Third Edition, Springer-Verlag, 2008.
  • J. O'Rourke, Computational Geometry in C, Second Edition, Campbridge University Press, 1998.
  • J.-D. Boissonnat, M. Yvinec, Géométrie Algorithmique, Ediscience international, Paris, 1995. (Перевод на англ.: J.-D. Boissonnat, M. Yvinec, Algorithmic geometry, Cambridge University Press, UK, 1998.)
  • Ф. Препарата, М. Шеймос, Вычислительная геометрия: Введение, М., Мир, 1989. (Перевод с англ.: F. Preparata, M. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985.)
  • S. L. Devadoss and J. O’Rourke, Discrete and Computational Geometry, Princeton University Press, 2011.
  • D. Mount, Lecture notes: CMSC 754 Computational Geometry, Dept. of Computer Science, University of Maryland, USA, Fall 2002.
Date and time Class|Name Venue|short Materials
16 February
11:15–12:50
Введение, Lecture ПОМИ РАН video
02 March
11:15–12:50
Выпуклая оболочка, Lecture ПОМИ РАН video
09 March
11:15–12:50
Выпуклая оболочка (окончание). Пересечение отрезков, Lecture ПОМИ РАН video
16 March
11:15–12:50
Пересечение геометрических объектов, Lecture ПОМИ РАН video
16 March
13:00–14:35
Пересечение полуплоскостей. Триангуляция многоугольника, Lecture ПОМИ РАН video
23 March
11:15–12:50
Триангуляция многоугольника (окончание), Lecture ПОМИ РАН video
23 March
13:00–14:35
Локализация точки на планарном подразбиении, Lecture ПОМИ РАН video
06 April
11:15–12:45
Локализация точки на планарном подразбиении (окончание), Lecture ПОМИ РАН video
13 April
11:15–12:50
Диаграмма Вороного, Lecture ПОМИ РАН video
13 April
13:00–14:30
Построение диаграммы Вороного, Lecture ПОМИ РАН video
20 April
11:15–12:50
Триангуляция Делоне, Lecture ПОМИ РАН video
27 April
11:15–12:50
Конфигурации прямых и двойственность в вычислительной геометрии, Lecture ПОМИ РАН video