Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский English

Вычислительная геометрия
Весна 2014, посмотреть все семестры

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

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

Список литературы: * 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.

Дата и время Название Место Материалы
16 февраля
11:15–12:50
Введение, лекция ПОМИ РАН видео
02 марта
11:15–12:50
Выпуклая оболочка, лекция ПОМИ РАН видео
09 марта
11:15–12:50
Выпуклая оболочка (окончание). Пересечение отрезков, лекция ПОМИ РАН видео
16 марта
11:15–12:50
Пересечение геометрических объектов, лекция ПОМИ РАН видео
16 марта
13:00–14:35
Пересечение полуплоскостей. Триангуляция многоугольника, лекция ПОМИ РАН видео
23 марта
11:15–12:50
Триангуляция многоугольника (окончание), лекция ПОМИ РАН видео
23 марта
13:00–14:35
Локализация точки на планарном подразбиении, лекция ПОМИ РАН видео
06 апреля
11:15–12:45
Локализация точки на планарном подразбиении (окончание), лекция ПОМИ РАН видео
13 апреля
11:15–12:50
Диаграмма Вороного, лекция ПОМИ РАН видео
13 апреля
13:00–14:30
Построение диаграммы Вороного, лекция ПОМИ РАН видео
20 апреля
11:15–12:50
Триангуляция Делоне, лекция ПОМИ РАН видео
27 апреля
11:15–12:50
Конфигурации прямых и двойственность в вычислительной геометрии, лекция ПОМИ РАН видео