Критерии (определения и проверки)
- Выпуклая оболочка множества точек $S$ — наименьшее выпуклое множество, содержащее $S$. Эквивалентно: пересечение всех выпуклых множеств, содержащих $S$, или множество всех выпуклых комбинаций точек из $S$.
- Точка $p$ лежит в выпуклой оболочке многогранника (многоугольника) тогда и только тогда, когда ее можно представить как невязко-отрицательную комбинацию вершин с суммой коэффициентов $1$.
- Для проверки ориентации (левый/правый поворот) трех точек $A(a_x,a_y),B(b_x,b_y),C(c_x,c_y)$ используется векторное (кросс) произведение:
$$\mathrm{cross}(A,B,C)=(b_x-a_x)(c_y-a_y)-(b_y-a_y)(c_x-a_x).$$ Знак этого выражения даёт направление поворота. Для выпуклого (ориентированного против часовой) многоугольника все последовательные тройки должны иметь $\mathrm{cross}\ge 0$ (или $\le 0$ в зависимости от ориентации), с учётом коллинеарности по требованию включения/исключения границ.
Основные алгоритмы (коротко, с идеей и сложностью)
- Джарвис (Gift wrapping)
- Идея: стартовая экстремальная точка, итеративно выбира самая «левую» относительно последней добавленной -> обводит оболочку.
- Сложность времени: $O(nh)$, где $h$ — число вершин оболочки.
- Память: $O(1)$ дополнительной (помимо хранения точек), результат в $O(h)$.
- Применимость: хорош для малого $h$ (тонкая оболочка), плох при большом $h$.
- Грэм (Graham scan)
- Идея: выбрать опорную точку (низшая по $y$), отсортировать остальные по полярному углу, проход стеком исключая правые повороты.
- Сложность: $O(n\log n)$ из-за сортировки; проход — $O(n)$.
- Память: $O(n)$ для сортировки, стек $O(h)$.
- Применимость: простой, надёжен при общем случае.
- Andrew / Monotone chain
- Идея: сортировать точки по $x$ (и по $y$ для одинаковых $x$), строить нижнюю и верхнюю цепи монотонным методом (аналог стековой проверки поворотов).
- Сложность: $O(n\log n)$; память: $O(n)$ (можно делать in-place).
- Практически предпочтителен за счёт простоты и стабильности.
- Quickhull
- Идея: рекурсивно делит множества по опорной хорде, отбирает внешние точки (аналог quicksort).
- Средняя сложность: $O(n\log n)$, худшая: $O(n^2)$.
- Память: рекурсивная, обычно $O(n)$.
- Практически быстрый на случайных данных; осторожно для специально выстроенных входов.
- Divide and Conquer (в т.ч. Kirkpatrick–Seidel)
- Идея: разделить по координате, рекурсивно найти оболочки и слить двумя выпуклыми цепями.
- Сложность: $O(n\log n)$; есть варианты с гарантией лучшего по $h$.
- Используется для параллелизации и теоретических границ.
- Chan’s algorithm
- Идея: комбинирует грубые группы и Jarvis, даёт оптимальную зависимость от $h$.
- Сложность: $O(n\log h)$ (лучше, когда $h\ll n$).
- Память: $O(n)$.
- Применимость: когда ожидается маленькое число вершин оболочки.
- Инкрементальные и случайные алгоритмы
- Инкрементально вставляют точки, поддерживают текущую оболочку; простой вариант $O(n^2)$, рандомизированные варианты дают $O(n\log n)$ в среднем.
- Полезны для динамических/онлайн задач; для полноценной динамики существуют сложные структуры с логарифмическими апдейтами.
Выбор алгоритма в зависимости от $n$, $h$, требований по времени и памяти
- Малые $n$ ($n$ до десятков тысяч): алгоритмы $O(n\log n)$ (Monotone chain, Graham) — просты и быстры на практике.
- Когда $h$ существенно меньше $n$: используйте алгоритмы с зависимостью от $h$ — Jarvis если $h$ очень мал, Chan’s для гарантированно $O(n\log h)$.
- Для очень больших $n$ и ограниченной памяти: Monotone chain in-place или внешняя сортировка + объединение; для потоковой обработки — онлайн/инкрементальные структуры.
- Для практической скорости на «случайных» данных: Quickhull часто очень быстрый; для худших случаев (вырожденные распределения, кольца) предпочтительны Graham/Andrew/Chan с гарантией.
- Для параллельных или распределённых задач: divide-and-conquer легко распараллеливается (параллельно сортировка и слияние оболочек).
- Для численной устойчивости: важен надёжный предикат ориентации; при целых координатах используйте целочисленные 64-битные вычисления или exact arithmetic; при вещественных — использовать расширенную точность/кораровку.
Практические замечания
- Обработка вырожденных случаев: коллинеарные точки — решать, включать ли внутренние точки границы (обычно исключают).
- Предварительная фильтрация: удаление внутренних точек (например, минимальный/максимальный по x/y) может ускорить на больших наборах.
- Реализация: Monotone chain — компактна и легко отлаживается; Quickhull — требует аккуратной реализации для устойчивости.
Краткая сводка сложностей (время / память)
- Jarvis: $O(nh)$ / $O(1)$ доп.
- Graham: $O(n\log n)$ / $O(n)$ - Monotone chain: $O(n\log n)$ / $O(n)$ (можно in-place)
- Quickhull: среднее $O(n\log n)$, худшее $O(n^2)$ / $O(n)$ - Chan: $O(n\log h)$ / $O(n)$
Если нужно — могу привести компактный псевдокод для выбранного алгоритма или советы по реализации и устойчивым предикатам.