Кружок обучения мастерству программирования при СПбГУ

Лекции группы A0 - Лекция 02 - про многоугольники

Краткий план лекции на тему "Геометрия многоугольников"

1. Выпуклые оболочки, не классические методы
2. Экстремальные задачи на выпуклых многоугольниках
3. Локализация точки
4. * Выпуклые оболочки
5. * Offline методы

Полный план лекции

1. Выпуклые оболочки, не классические методы
1. Алгоритм Quick (в среднем работает за O(N), на окружности за O(NlogN), в худшем за O(NlogMax) [целочисленный и вещественный случаи])
2. Метод разделяй и властвуй [построение общих касательных]
2. Экстремальные задачи на выпуклых многоугольниках
1. Построение общих касательных за O(n) [2 указателя, из каждой точки первого строим касательную ко второму]
2. Построение касательных из точки за O(logn) [ищем экстремумы функции "угол"]
3. Ищем 2 точки по разные стороны от прямой + 2 бинпоиска на поиск корней.
   1. 2 точки = 2 экстремума функции "расстояние до прямой"
   2. первая точка = любая, вторая ищется одним бинпоиском
   3. Вариант с предподсчетом за O(n) [или даже за O(1)]. Сортировка сторон + 2 бинпоиска для получения экстремальных точек.
4. Поиск ближайшей точки мн-ка к данной за O(logn) [строим касательные, получаем лицевую часть и по ней 3-Search]
5. Поиск разделяющей прямой = поиск двух ближайших точек [автоматически получается прямая max удаленная от мн-ков]
6. Поиск двух ближайших точек за O(n^2), за O(nlogn)
3. Локализация точки
1. Проверка принадлежности точки многоугольнику за O(n). Пуск горизонтального луча, отрезок = [minY,maxY).
2. Поиск точки внутри мн-ка, за O(1) для выпуклого или с известной ориентацией, за O(n) в общем случае.
3. Проверка для выпуклого за [O(1), O(logn)] - предподсчет, запрос.
4. Проверка для невыпуклого за [O(n^2), O(logn)].
5. Проверка для невыпуклого за [O(nlogn), O(log^2n)] (вариант с сортировкой по углу, с сортировкой по координатам)
6. Пересчет выпуклой оболочки online, суммарное время = O(nlog^2n), optimization to O(nlogn) с помощью внутренней точки.
4. * Выпуклые оболочки
1. * O(nk) Алгоритм заворачивания подарка (Jarvis) [3D обобщение, решение задачи для кругов]
2. * O(nlogn) Сортировки по углу (Graham) [улучшение = сортировкой по координате]
3. * O(nlogk) Гибрид Jarvis + Graham = Chan
4. * Алгоритм Melkman-а построения выпуклой оболочки от мн-ка за O(n).
5. * Offline методы
1. * K точек. Определить, где они находятся, относительно невыпуклого N-угольнике за O(NlogN + KlogK).
2. * В случае выпуклого O(N + KlogK)
3. * Поиск экстремальных точек для K прямых и N-угольника за O(N + KlogK)