Как построить выпуклую оболочку n точек на плоскости за O(n³)? А за O(n log n)? Как распрямить в плоскости без самопересечений складной метр? Как проложить кратчайший маршрут между двумя точками при наличии препятствий? Вот типичные задачи, которыми мы будем заниматься.

Программа курса

1. Поиск взаимных пересечений отрезков;
2. Элементы линейной алгебры: ориентация и знак определителя матрицы;
3. Алгоритмы построения выпуклой оболочки: метод обхода Грэхема; метод заворачивания подарка (метод Джарвиса), «разделяй и властвуй», «быстрая оболочка» и др.
4. Элементы комбинаторной геометрии: существование дигонали, существование триангуляции, задача о картинной галерее.
5. Алгоритм триангуляции простого полигона. «Отрезание ушей». Монотонные многоугольники. Разбиение простого многоугольника на монотонные.
6. Элементы топологии: теорема Борсука-Улама, дискретная теорема о сэндвиче с ветчиной, теорема Шнирельмана о раскрашенной сфере.
7. Продвинутые современные вещи: укорачивающий кривую поток, псевдотриангуляции, распрямление полигонального шарнирного механизма, алгоритм «игра в камушки».