Полуплоскости и рандомизированные алгоритмы (24 ноября 2016)

1. Рандомизированное
1. Покрывающий круг на плоскости
2. Проверка графа на рёберную трёхсвязность
3. Random-Walk на графах, на d-регулярных графах


2. Полуплоскости
1. Пересечение верхнеогебающих: y ≥ kx + b, сортировка по (k,b), стек
2. Построение верхней части выпуклой оболочки: сортировка по (x,y), стек
3. Биекция (x,y) ↔ (k,-b). Леммы: сохраняются отношения "ниже" и "пересекаются".
4. Теорема: верхняя часть выпуклой оболочки ↔ пересечение верхних полуплоскостей
5. Общий случай пересечения полуплоскостей: повернули на случайный угол (чтобы не было вертикальных), нашли две части, двумя указателями нашли пересечение