Алгоритм Чана: как строить выпуклую оболочку за O(n log h)

Алгоритм Чана (Chan's algorithm, опубликован Тимоти Чаном в 1996 году) строит выпуклую оболочку $n$ точек на плоскости за время $O(n \log h)$, где $h$ - число вершин самой оболочки. Это output-sensitive результат: чем меньше оболочка, тем быстрее работает алгоритм, причём асимптотика оптимальна по нижней оценке для output-sensitive класса. Идея красивая: взять Graham scan, который силён на $O(n \log n)$, и Jarvis march, который силён на $O(nh)$, и комбинировать их так, чтобы каждый компенсировал слабость другого. Параметр $m$ - гипотетический «угаданный» размер оболочки - подбирается через геометрическую прогрессию с early termination.

Мотивация: чем плохи Graham и Jarvis по отдельности

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

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

Возникает вопрос: можно ли получить алгоритм, который всегда не хуже обоих - то есть $O(n \log h)$? Output-sensitive нижняя оценка $\Omega(n \log h)$ известна давно. Первый match - Kirkpatrick–Seidel «ultimate planar convex hull» (1986) - достигает $O(n \log h)$, но через сложный bridge-finding с медианой и prune-and-search. Чан в 1996 нашёл намного более простую конструкцию из двух стандартных кубиков.

Идея: Graham внутри, Jarvis снаружи

Пусть нам как-то заранее «угадан» размер оболочки $m \approx h$. Алгоритм Чана делает следующее.

Шаг 1. Разбиение и локальные оболочки. Разбить $n$ точек на $\lceil n/m \rceil$ групп по $m$ точек. В каждой группе построить локальную выпуклую оболочку обычным Graham scan за $O(m \log m)$. Суммарно по всем группам - $O((n/m) \cdot m \log m) = O(n \log m)$.

Шаг 2. Jarvis march по группам. Запустить Jarvis на «макроуровне»: на каждом шаге надо найти следующую вершину глобальной оболочки. Делается это так - для каждой из $n/m$ локальных оболочек найти касательную из текущей вершины к этой оболочке. Касательная к выпуклому многоугольнику размером $m$ ищется бинарным поиском за $O(\log m)$. Среди $n/m$ кандидатов выбрать «самого правого» - $O(n/m)$ сравнений. Один шаг Jarvis - $O((n/m) \log m)$. Всего шагов - $h$, итого $O((nh/m) \log m)$.

Сложение. $O(n \log m) + O((nh/m) \log m)$. При $m = h$ получаем $O(n \log h) + O(n \log h) = O(n \log h)$. То есть если бы мы знали $h$, всё бы сошлось.

Угадывание $h$ через геометрическую прогрессию

Проблема - мы не знаем $h$ заранее: оно и есть то, что мы хотим вычислить. Решение Чана - пробовать $m$ по геометрической прогрессии $m_t = 2^{2^t}$ (или проще - $m_t = 2, 4, 8, 16, \ldots$ с двойным возведением) и запускать алгоритм с early termination: если после $m$ шагов Jarvis обход не замкнулся, значит, $h > m$, прерываем и пробуем следующее $m$.

Точнее, на итерации $t$ выставляем $m = \min(2^{2^t}, n)$, выполняем шаги 1 и 2, но ограничиваем Jarvis-цикл $m$ итерациями. Если оболочка построилась (вернулись в стартовую вершину за $\leq m$ шагов) - выводим её и стоп. Если нет - увеличиваем $t$ и повторяем.

Затраты по итерациям складываются в геометрический ряд:

$T = \sum_{t=0}^{\lceil \log_2 \log_2 h \rceil} O(n \log m_t) = O\!\left(n \sum_{t=0}^{\log\log h} 2^t\right) = O(n \cdot 2^{\log\log h + 1}) = O(n \log h).$

Последняя итерация даёт $m_t \geq h$, и алгоритм гарантированно завершается. Сумма доминируется последним членом - это и есть итоговое $O(n \log h)$.

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

Локальные оболочки шага 1 содержат все граничные точки своих групп (Graham scan корректен). Любая вершина глобальной оболочки $\mathrm{conv}(S)$ - граничная точка своей группы (если бы была внутренней, нашлась бы группа-сосед с точкой левее/правее, противоречие). Значит, каждая вершина глобальной оболочки присутствует хотя бы в одной локальной.

Касательная из точки $p$ к выпуклому многоугольнику размером $m$ корректно находится бинарным поиском по углам. Шаг Jarvis выбирает «самую правую» точку среди всех касательных - это и есть следующая глобальная вершина. Обход замыкается за $h$ шагов, потому что глобальная оболочка имеет ровно $h$ вершин.

Early termination не теряет корректности: если оболочка не замкнулась за $m$ шагов, мы выкидываем промежуточные результаты и перезапускаем с большим $m$. Не запускается ни одной лишней операции на корректном выходе.

Итоговая сложность $O(n\log h)$

Соберём:

• Шаг 1 на итерации $t$ - $O(n \log m_t)$.
• Шаг 2 на итерации $t$ - $O((n m_t / m_t) \log m_t) = O(n \log m_t)$ (потому что мы ограничили Jarvis $m_t$ шагами).
• Итерации $t = 0, 1, \ldots, \lceil \log_2 \log_2 h \rceil$.

Каждая итерация - $O(n \log m_t) = O(n \cdot 2^t)$. Сумма геометрическая, доминируется последним членом, который $O(n \log h)$. Итог: $O(n \log h)$.

Память - $O(n)$: хранятся точки, локальные оболочки, текущая глобальная вершина. Никаких дополнительных структур.

Сравнение с Kirkpatrick–Seidel

Оба алгоритма достигают $O(n \log h)$ и оба оптимальны output-sensitive. Различия:

• Конструкция. Чан - два знакомых кубика (Graham + Jarvis) и геометрическая прогрессия. Kirkpatrick–Seidel - bridge-finding с prune-and-search на медиане, $2$-fold marriage-before-conquest. Реализация Чана умещается в 80 строк C++, K-S - 200+.
• Константа. У Чана константа выше в Jarvis-шаге (бинарный поиск касательной для каждой группы), но проще структура памяти. На практике в библиотеках (CGAL, Boost.Geometry) чаще берут Чана или Andrew's monotone chain - K-S редко.
• 3D-обобщение. Чан обобщается до $O(n \log h)$ в 3D (Chan 1996 же), K-S - нет.

Поэтому Чан - фактический рабочий «output-sensitive ultimate» алгоритм.

Когда брать алгоритм Чана

• Огромные облака точек с малой оболочкой. GPS-треки, LiDAR-сканы, выборки из равномерного распределения на квадрате (там $h = O(\log n)$ в среднем). Чан даёт $O(n \log \log n)$, Graham - $O(n \log n)$.
• Стримы сенсоров. Когда $n$ велико, а граница мала и заранее неизвестна - Чан адаптируется.
• 3D convex hull в варианте Chan 1996 - $O(n \log h)$ в 3D, единственный простой output-sensitive.

Не брать, если $h \approx n$ (точки на окружности) - там Graham/Andrew проще и константа меньше. Также не брать, если важна устойчивость к коллинеарным случаям без специальной обработки - Чан наследует все подводные камни и Graham, и Jarvis сразу.

Типовые задачи

• Минимальный охватывающий многоугольник. Когда нужна только сама оболочка для дальнейших операций (диаметр, площадь, проверка вхождения).
• Broad-phase коллизии в физике. Convex hull mesh как грубое приближение формы.
• GIS-аналитика. Ареал наблюдений по тысячам/миллионам отметок.
• Кластеризация в ML. Convex hull кластера для визуализации и проверки разделимости.
• Олимпиадные задачи. При $n \geq 10^6$ и заранее малом $h$ Чан проходит, Graham - нет.

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

• Берут $m_t = 2^t$ вместо $m_t = 2^{2^t}$. Тогда число итераций - $\log h$, и сумма $\sum n \log 2^t = O(n \log^2 h)$ - на $\log$ хуже оптимума.
• Не ограничивают Jarvis $m$ шагами. Без early termination первая же итерация с $m < h$ просто зациклится или построит мусор; алгоритм перестаёт быть output-sensitive.
• Используют линейный поиск касательной вместо бинарного. Касательная к выпуклому многоугольнику размером $m$ ищется за $O(\log m)$ - это критично для асимптотики.
• Не сжимают дубликаты и не обрабатывают коллинеарные точки. Те же баги, что в Graham и Jarvis, унаследованы целиком.
• Считают $cross$ с плавающей точкой при больших координатах. Целочисленный $\text{int64}$ обязателен, иначе знак поворота врёт.

FAQ

Чем Chan's algorithm лучше Kirkpatrick–Seidel при одинаковой $O(n \log h)$? Реализация. Чан - это пять-семь страниц учебника с двумя стандартными кубиками. K-S - bridge-finding на медиане, prune-and-search, $2$-fold conquer; в учебниках занимает раздел на 20 страниц. На практике Чан реализован в CGAL и широко используется; K-S остаётся в основном теоретическим результатом. Асимптотика одинаковая, константа у Чана чуть выше, но кодоёмкость в разы меньше.

Можно ли построить трёхмерную выпуклую оболочку Чаном? Да. В той же работе 1996 года Чан показал $O(n \log h)$ для 3D через тот же приём - разбить на группы, локально построить $O(n \log n)$ или $O((n/m) \cdot m \log m)$ оболочкой, обходить «снаружи» с касательными плоскостями. В 3D output-sensitive нижняя оценка тоже $\Omega(n \log h)$, и Чан её достигает.

Что выбрать на собеседовании, если просят convex hull? Сначала уточните: «Знаем ли мы что-то про $h$?». Если нет - Andrew's monotone chain ($O(n \log n)$, проще Graham и стабильнее численно). Если ожидается малая оболочка на больших данных - Chan ($O(n \log h)$). На полу-устной задаче можно обойтись Graham - все его знают наизусть. Чана упоминают, если интервьюер хочет услышать про output-sensitive.

Коротко

Алгоритм Чана (1996) - output-sensitive алгоритм выпуклой оболочки на плоскости со сложностью $O(n \log h)$, где $h$ - число вершин оболочки. Идея: разбить $n$ точек на группы по $m$ и в каждой построить локальную оболочку Graham scan за $O(m \log m)$; затем Jarvis march по группам, на каждом шаге ища касательную бинарным поиском за $O(\log m)$. При $m = h$ суммарно - $O(n \log h)$. Значение $h$ заранее неизвестно, поэтому $m$ перебирают по двойной геометрической прогрессии $m_t = 2^{2^t}$ с early termination. Альтернатива той же асимптотики - Kirkpatrick–Seidel, но он значительно сложнее в реализации. Чана используют на больших облаках точек с малой оболочкой, в 3D-обобщении и в библиотеках вычислительной геометрии.