Комбинаторика и топология — совместный семинар ВШМ и лаборатории комбинаторных и геометрических структур ФПМИ МФТИ

Пока решили время семинара сделать плавающим — либо по пятницам с 15:30 до 17:05 (ауд.430ГК), либо по субботам с 13:55 до 15:30 (ауд.322АдмК).

Когда: суббота 20 сентября, 13:55
Где: Административный корпус, ауд.322

Доклад:

Алексей Фахрутдинов,
"Алгоритм построения ham-sandwich разрезов и приложение к ортогональному дележу на плоскости"

Одним из следствий теоремы Борсука-Улама является так называемая теорема о бутерброде: произвольные n множеств в R^n можно одновременно разделить одним разрезом-гиперплоскостью пополам. На семинаре мы обсудим статью [Lo, Matoušek, Steiger, Algorithms for Ham-Sandwich Cuts], подробно разобрав оптимальный алгоритм нахождения такого разреза на плоскости (n=2) за линейное время. Так же будет приведен общий план построения алгоритма в случае n>2 и приложение развитой в статье техники к задаче о разделении множества на плоскости ортогональным разрезом на четыре равные части, которая может быть решена за линейное время.


Страница семинара: https://old.mccme.ru/ium/s23/ryabichev/f25-mipt-topkomb.html
Трансляции семинара не планируется, но, возможно, мы выложим запись.

#ВШМ_ФПМИ_топкомб