Планарные графы и рандомизированные алгоритмы (17 ноября 2016)

1. Планарные графы
1. Физическая модель укладки
2. Пересечение/объединение k многоугольников из n вершин за O(kn²logn)
3. Разбиение плоского графа на грани
4. Persistent scanline: задача локализации в online
2. Рандомизированные
1. Лас-Вегас (число, которое встречается >1/2 раз, максимальная арифметическая подпоследовательность)
2. Монте-Карло на примере пересечения/объединения n кругов (выпуклых фигур)
3. Квадро-Дерево (на примере той же задачи, чтобы показать, что Монте-Карло хорош на больших размерностях)
4. Хеширование Кукушки и совершенное хеширование
5. Алгоритм пересечения полупространств за O(d!*n)
3. Осталось на будушее
1. Random-Walk на графах, на d-регулярных графах
2. Проверка графа на рёберную трёхсвязность