Санкт-Петербург, 199178, Россия, 14-ая линия Васильевского острова, дом 29
(812) 363-68-71, (812) 363-68-72
ru

Геометрические алгоритмы

2019 – 2020, V, VII семестр

Информация по курсу

Геометрические алгоритмы — это алгоритмы для решения вычислительных задач о дискретных геометрических объектах. Это обширная область, которая настолько богата разными техниками, что некоторые университеты предлагают курс геометрических алгоритмов в качестве первого
базового курса алгоритмов. В рамках данного спецсеминара мы рассмотрим отдельные темы, отражающие некоторые классические результаты и современные тенденции области. Темы в основном будут браться из списка (возможны изменения в связи с интересами участников и прослушанными ранее курсами):

-Близостные геометрические графы на плоскости и их построение,

-Близостные геометрические графы и другие алгоритмы на поверхности выпуклых многогранников

-Геометрические спаннеры и роутинг на геометрических графах,

-Планарные сепараторы и геометрический локальный поиск

-Рандомизированные геометрические алгоритмы и техники их дерандомизации

-Приближенные геометрические алгоритмы

-Алгоритмы в моделях, альтернативных RAM: limited workspace, bounded universe.

-Geometric Folding

-Визуализация графов (graph drawing) и связанные с ней алгоритмы

-Геометрические структуры данных