Конспект: выпуклая оболочка

Понятия

Выпуклое множество - вместе с любыми двумя точками содержит отрезок между ними.

Выпуклая оболочка набора точек - наименьший выпуклый многоугольник, содержащий все точки; вершины - некоторые точки набора. Отрезок - её ребро, если все остальные точки по одну сторону от него.

Чувствительный к выходу алгоритм - его время зависит от размера ответа: здесь от числа вершин h.

Опорная прямая касается многоугольника и оставляет его по одну сторону. Антиподальная пара - вершины на двух параллельных опорных прямых.

Что унести

ЗАВОРАЧИВАНИЕ ПОДАРКА (Джарвис)              O(n · h)
старт - самая левая (при равенстве нижняя) точка
шаг: кандидат = любая; для каждой p: если p справа от
     (текущая → кандидат) - кандидат = p; ноль - брать дальнюю
12 гвоздей: 7 вершин, 77 поворотов
парабола из 80 точек: 6320 поворотов (h = n, квадрат)

ЦЕПОЧКА ЭНДРЮ (вариант Грэхема)              O(n · log n)
t = sorted(точки)                  по (x, y)
нижняя: слева направо, снимать вершину стека,
        пока поворот(стек[-2], стек[-1], p) <= 0
верхняя: то же справа налево
оболочка = нижняя[:-1] + верхняя[:-1]
стеки линейны: каждая точка снимается не больше раза
<= 0 выбрасывает точки на рёбрах, < 0 оставляет
    (тогда «все на одной прямой» даёт повторы)
повторы точек убрать заранее; одна точка - отдельный случай
парабола из 80 точек: 156 поворотов = 2n − 4

НИЖНЯЯ ГРАНИЦА
числа x → точки (x, x²) → оболочка выдаёт их по возрастанию
значит, оболочка не дешевле сортировки: Ω(n · log n)
модель: решения знаками многочленов от координат (Бен-Ор, 1983)
обход 1: маленькие целые координаты - сортировка подсчётом
обход 2: малое h - Чан (1996), O(n · log h),
         m = 4, 16, 256, … - квадрат прежнего
случайные точки: в квадрате h ~ (8/3) ln n, в круге ~ n^(1/3)
    1600 точек: 21 и 43 вершины
3D: размер O(n) граней (Эйлер), scipy.spatial.ConvexHull - Qhull

НА ГОТОВОЙ ОБОЛОЧКЕ
диаметр: вращающиеся калиперы, O(h); указатель на дальнюю
         вершину только вперёд; сравнивать квадраты
         200 датчиков, h = 45: 220 поворотов против 19 900 пар
ширина, наименьший охватывающий прямоугольник - тем же обходом
точка внутри выпуклого: двоичный поиск по вееру из H[0],
         O(log h) - около 8 поворотов на 45 вершинах
обе вещи только для ВЫПУКЛОГО

Ловушки джокера

Нет правила для нулевого поворота. В заворачивании - бери дальнюю точку, иначе ответ зависит от порядка входа.

Сортировка только по x. Точки с одним x встают как попало, и оболочка теряет вершину.

Нестрогое снятие без мысли о прямой. Все точки на одной прямой возвращаются дважды.

Забыл повторы. Две копии одной точки дают поворот через нулевой вектор.

«Нашёл линейную оболочку». В тестах было малое h или маленькие координаты, а не новая математика.

Калиперы на невыпуклом контуре. Сначала оболочка, потом калиперы.

Указатель с нуля на каждом ребре. Это снова h².

Проверь себя

Почему отрезок - ребро оболочки ровно тогда, когда все точки по одну сторону? Сколько стоит заворачивание подарка и на каких входах оно квадратично? Почему стеки в цепочке Эндрю линейны? Что меняет условие снятия <= 0 против < 0? Как парабола превращает сортировку в оболочку и в какой модели верна граница n · log n? Как работает алгоритм Чана и зачем m возводят в квадрат? Почему указатель калиперов движется только вперёд?

Оболочка в 3D: удаляют видимые грани и достраивают треугольники по горизонту; граф конфликтов и случайная вставка дают ожидаемые O(n log n). У триангулированной оболочки 2v-4 граней.

Понятия

Что унести

Ловушки джокера

Проверь себя

Комментарии

Оставить комментарий