Алгоритм Грэхема: строим выпуклую оболочку точек

Алгоритм Грэхема (Graham scan, опубликован Рональдом Грэхемом в 1972 году) - классический способ построить выпуклую оболочку конечного набора точек на плоскости за время $O(n \log n)$. Идея простая и красивая: выбрать заведомо граничную опорную точку, отсортировать остальные по полярному углу относительно неё и обойти их одним проходом, поддерживая стек кандидатов в вершины оболочки и каждый раз проверяя направление поворота. Это первая историческая реализация выпуклой оболочки с оптимальной по нижней оценке асимптотикой и до сих пор - учебный эталон при разборе вычислительной геометрии.

Постановка задачи

Дано множество $S = \{p_1, p_2, \ldots, p_n\}$ из $n$ точек на плоскости. Выпуклая оболочка $\mathrm{conv}(S)$ - наименьшее выпуклое множество, содержащее все точки $S$. Геометрически это многоугольник, чьи вершины - подмножество $S$, такой что все остальные точки лежат внутри или на границе этого многоугольника. Задача - выдать вершины оболочки в порядке обхода (обычно против часовой стрелки), не пропустив ни одной граничной точки и не включив ни одной внутренней.

Нижняя оценка задачи - $\Omega(n \log n)$: построение выпуклой оболочки сводится к сортировке (если расположить $n$ чисел $x_i$ как точки $(x_i, x_i^2)$ на параболе, их оболочка возвращает $x_i$ в отсортированном порядке). Значит, алгоритмы быстрее $O(n \log n)$ в общем случае невозможны без дополнительных предположений на вход.

Идея алгоритма Грэхема

Алгоритм Грэхема выбирает опорную точку $p_0$ - ту, у которой минимальная координата $y$ (а при равных $y$ - минимальная $x$). Такая точка заведомо принадлежит выпуклой оболочке: ниже неё точек нет, значит, она лежит на нижней границе. Затем все остальные точки сортируются по полярному углу относительно $p_0$ - то есть по углу луча $p_0 p_i$ с положительным направлением оси $x$. После сортировки получается список $p_0, p_1, p_2, \ldots, p_{n-1}$ - обход начинается из $p_0$ и идёт против часовой стрелки.

Дальше включается стек $\mathcal{H}$ кандидатов. В стек кладутся $p_0, p_1, p_2$. Для каждой следующей точки $p_k$ проверяется ориентация тройки (предпоследняя вершина стека, верхушка стека, $p_k$). Если поворот левый (против часовой) - точка добавляется в стек. Если поворот правый или нулевой (по часовой или коллинеарный) - верхушка стека выкидывается, и проверка повторяется заново с новой верхушкой. После прохода всех точек стек содержит вершины выпуклой оболочки в порядке обхода.

Проверка поворота через cross product

Ключевая операция алгоритма - определение, куда повернула ломаная в очередной точке. Для трёх точек $a = (a_x, a_y)$, $b = (b_x, b_y)$, $c = (c_x, c_y)$ вычисляется псевдоскалярное произведение векторов $\vec{ab}$ и $\vec{ac}$:

$\text{cross}(a, b, c) = (b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x).$

Знак определяет ориентацию:

• $\text{cross} > 0$ - поворот против часовой (левый), точка $c$ лежит слева от прямой $ab$.
• $\text{cross} < 0$ - поворот по часовой (правый), точка $c$ справа.
• $\text{cross} = 0$ - три точки коллинеарны.

Операция целочисленная, если все входные координаты целые, - никаких тригонометрий, никаких накапливающихся ошибок плавающей точки. Это одна из причин, почему алгоритм Грэхема устойчив численно и удобен для соревновательного программирования.

Корректность

Утверждение: после прохода стек содержит ровно вершины выпуклой оболочки в порядке против часовой стрелки. Доказательство идёт индукцией по числу обработанных точек.

База: точки $p_0, p_1$ - два соседа по углу, $p_1$ - следующая граничная точка против часовой. Шаг: пусть после $k - 1$ шагов на стеке - корректная выпуклая оболочка точек $\{p_0, \ldots, p_{k-1}\}$ в порядке обхода. При добавлении $p_k$ алгоритм откатывает с вершины все точки, образующие правый или нулевой поворот с $p_k$ - то есть все точки, оказавшиеся внутри ломаной $\ldots, p_k$. Любая такая точка не может быть вершиной финальной оболочки. После откатов сверху лежит точка, от которой переход к $p_k$ - левый поворот; новый кусок ломаной остаётся выпуклым.

Сортировка по полярному углу гарантирует, что точки добавляются в обход именно против часовой стрелки; опорная точка $p_0$ с минимальным $y$ гарантирует, что все полярные углы лежат в диапазоне $[0, \pi]$ и сортировка корректно их упорядочивает.

Сложность $O(n\log n)$

Затраты по шагам:

1. Поиск опорной точки $p_0$ - $O(n)$ одним проходом.
2. Сортировка $n - 1$ точек по полярному углу - $O(n \log n)$ через любой стандартный $\log$-сорт (сравнения через cross product, не через atan2).
3. Обход и работа со стеком - амортизированно $O(n)$: каждая точка попадает в стек ровно один раз и выкидывается из него не более одного раза. Каждая итерация внутреннего while уменьшает размер стека, общее число выкидываний не превышает $n$.

Итого $O(n \log n)$, причём константа доминирует на сортировке. Это оптимально по нижней оценке.

Сравнение с другими алгоритмами

Jarvis march (gift wrapping, 1973) - $O(nh)$, где $h$ - число вершин оболочки. Идея: каждый раз искать самую «правую» точку среди оставшихся, пока не вернёмся в начало. При $h = O(\log n)$ быстрее Грэхема; при $h = \Theta(n)$ (точки на окружности) деградирует до $O(n^2)$. Берут, когда $h$ заведомо мало или нужен потоковый вывод вершин по одной.

Andrew's monotone chain (1979) - модификация Грэхема: сортирует по $x$ (а не по углу), строит верхнюю и нижнюю полуоболочки и склеивает. Тоже $O(n \log n)$, но численно стабильнее и кодируется короче - в продакшене на C++ и Python чаще используют именно его.

QuickHull (1977) - рекурсивный аналог быстрой сортировки: находит крайние точки по $x$, делит остальные относительно хорды и обрабатывает рекурсивно. Среднее $O(n \log n)$, худший случай $O(n^2)$. Эффективен на разбросанных данных, плох на точках, плотно лежащих на окружности.

Chan's algorithm (1996) - output-sensitive $O(n \log h)$. Объединяет Грэхема на подмножествах с шагом Jarvis по ним. Лучше всех при заранее неизвестном маленьком $h$, но сложнее в реализации.

Подводные камни

Коллинеарные точки. Когда несколько точек лежат на одном луче из $p_0$, их полярный угол одинаков и сортировка даёт неоднозначный порядок. Починка - при равных углах сортировать по расстоянию от $p_0$. Если нужна строгая оболочка (только настоящие вершины), при $\text{cross} = 0$ откатывают предыдущую точку.

Совпадающие точки. Дубликаты убирают заранее, иначе сортировка выдаёт ноль для пары и обход уходит в цикл выкидываний.

Менее трёх точек. Алгоритм требует $n \geq 3$; при $n = 1$ оболочка - сама точка, при $n = 2$ - отрезок. Эти случаи обрабатывают отдельной веткой.

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

Где применяется

• Компьютерная графика. Bounding shape для коллизий, упрощённая граница спрайтов и моделей - компактное «грубое» приближение формы, по которому быстро проверяются пересечения.
• GIS и картография. Минимальная выпуклая область наблюдений: ареал вида, зона покрытия датчиков, граница облака GPS-отметок.
• Кластеризация в ML. Граница кластера через convex hull точек кластера - для визуализации и для проверки «попадает ли новая точка внутрь».
• SVM и оптимизация. Выпуклые оболочки классов - стандартный способ анализа линейной разделимости: если оболочки не пересекаются, классы разделимы.
• Физические движки. Convex hull triangle mesh как broad-phase bounding до точного теста коллизий.
• Олимпиадные задачи. Диаметр оболочки через rotating calipers, минимальный охватывающий прямоугольник, ближайшая пара точек.

Частые ошибки

• Считают полярный угол через atan2 и сравнивают float. Числовая ошибка превращает соседние углы в произвольный порядок. Правильно - сравнивать через cross product двух векторов: $\text{cross}(p_0, p_i, p_j) > 0$ означает «$p_j$ левее, угол меньше».
• Не обрабатывают коллинеарные точки. Алгоритм без явной ветки на $\text{cross} = 0$ может оставить точку в оболочке или выкинуть, как повезёт. Решите заранее: нужна строгая оболочка или допускается коллинеарность на стороне.
• Берут случайную опорную точку. Опорной должна быть гарантированно граничная точка (самая нижняя/левая), иначе сортировка по полярному углу не покрывает всю окружность $2\pi$.
• Сравнивают cross с нулём как float. Если координаты целые - считайте в int64, иначе при больших значениях получите переполнение и неправильный знак.
• Забывают сжать дубликаты. Несколько одинаковых точек ломают сортировку и порождают зацикливание на выкидываниях.

FAQ

Чем алгоритм Грэхема отличается от Andrew's monotone chain? Идеи одинаковые - отсортировать точки и собрать оболочку линейным проходом со стеком. Различие в порядке сортировки. Грэхем - по полярному углу относительно опорной точки. Andrew - по координате $x$, строит верхнюю и нижнюю полуоболочки и склеивает. У Andrew проще обработка коллинеарных случаев, у Грэхема приятнее интуиция.

Когда выгоднее использовать Jarvis march вместо Грэхема? Когда заранее известно, что число вершин оболочки $h$ мало, скажем $h = O(\log n)$. Jarvis работает за $O(nh)$, и при таком $h$ это $O(n \log n)$ - как Грэхем, но с меньшей константой и без сортировки (что удобно при потоковых данных). Если же оболочка может содержать почти все точки - Jarvis деградирует до $O(n^2)$, и Грэхем выигрывает.

Можно ли построить трёхмерную выпуклую оболочку алгоритмом Грэхема? Прямо - нет. Полярный угол на сфере и стек кандидатов уже не задают однозначного обхода. Для 3D используют QuickHull, incremental hull или divide and conquer - асимптотика лучших алгоритмов $O(n \log n)$ для случайных распределений и $O(n^2)$ в худшем случае на специально подобранных входах.

Коротко

Алгоритм Грэхема (1972) строит выпуклую оболочку $n$ точек на плоскости за $O(n \log n)$. Шаги: выбор опорной точки с минимальным $y$, сортировка остальных по полярному углу, проход стеком с проверкой поворота через cross product. При левом повороте точка добавляется, при правом - верхушка стека выкидывается. Сложность доминирует сортировкой; обход со стеком - амортизированно $O(n)$. Сравнимые альтернативы - Jarvis march ($O(nh)$), Andrew's monotone chain ($O(n \log n)$, проще), QuickHull (среднее $O(n \log n)$). Применяется в компьютерной графике, GIS, кластеризации, физических движках и олимпиадных задачах.