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

Лекции группы A0 - Лекция 09 - Рандом + Геометрия (Сергей Копелиович)

Note: Звездочкой отмечены темы, на которые на лекции времени не хватило.

Краткий план лекции "Рандом + Геометрия"

  1. Пересечение полуплоскостей (за O(NlogN) и более простые методы)
  2. Линейный рандом (задачи, решающиеся за линейное время с помощью слова random)
  3. 3D Convex Hull (за O(NlogN) и более простые методы)

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

  1. Пересечение полуплоскостей
    1. Простой метод за O(N^2).
    2. Метод со стэком за O(NlogN).
      1. Пересечение = последовательность индексов полуплоскостей
      2. Сортировка по углу + удаление одинаковых по углу
      3. 2 случая - бесконечное или конечное пересечение
      4. Собственно стэк, снятие со стэка только если ang1 - ang3 < PI.
      5. В случае цикла: добавить полуплосоксти 2 раза по циклу. Пройтись по полученному стэку до первого повторения
    3. Алгоритм половинного деления плоскости
    4. Обобщение последнего до D-мерного случая
    5. Задача Линейного Программирования = пересечение полупространств * бинпоиск по ответу (найти хотя бы одну точку пересечения)
  2. Линейный рандом
    1. Задача Линейного Программирования в D-мерном пространстве за O(D!*N) [читай O(n)!]
    2. Алгоритм Лас-Вегаса выбора наиболее вероятного элемента за O(N) без доп.памяти
    3. Покрытие N точек на плоскости окружностью минимального радиуса за O(N), обобщение до 3D
  3. 3D Convex Hull
    1. Обзор различных решений (Incremental, Merge, Заворачивание подарка)
    2. * Решение за O(NK), где K --- число вершин ответа (заворачивание)
    3. * Рандомизированное решение за O(NlogN) (incremental)