Выпуклая оболочка

Цели урока

• Понимать Graham Scan: сортировка + стек + правые повороты
• Сравнивать Graham Scan и Jarvis March в зависимости от h
• Объяснять Chan's Algorithm и почему 2^(2^t) а не простое удвоение
• Понимать incremental hull для streaming данных

Предварительные знания

• Points, Segments, Polygons

Google Maps: 1 маршрут - алгоритм Дейкстры на графе с 50M+ узлов. Uber за 200мс находит ближайшего из тысяч водителей. Tesla Autopilot: point cloud из LiDAR -> выпуклая оболочка -> obstacle detection за 10ms. Вычислительная геометрия - это production infrastructure.

• **Tesla Autopilot:** LiDAR создаёт 100K точек/сек, convex hull препятствий строится за <10ms для collision avoidance
• **GJK Algorithm (game physics):** Unreal Engine, Unity - convex hull каждого rigid body объекта для collision detection
• **Computer vision:** bounding convex hull региона интереса - YOLO, Mask R-CNN используют для object detection
• **GPS tracking:** Uber, Lyft - incremental hull для отслеживания зоны покрытия водителей в реальном времени
• **Кластеризация ML:** визуализация границ кластеров в sklearn - convex hull каждого кластера в feature space
• **Робототехника (Boston Dynamics):** path planning - выпуклая оболочка препятствий определяет запретные зоны

Шамос, Хоэй и рождение вычислительной геометрии

В 1975 году Майкл Шамос и Дэн Хоэй опубликовали работу «Closest-point problems» - одну из первых в области, которую они назвали «computational geometry». В 1985 Шамос совместно с Франко Препаратой написал книгу **«Computational Geometry: An Introduction»** - основополагающий учебник, где convex hull занял центральное место. До их работ геометрические алгоритмы существовали разрозненно. Они создали дисциплину.

Graham Scan

Google Maps: один маршрут - алгоритм Дейкстры на графе с 50M+ узлов. Uber за 200мс находит ближайшего из тысяч водителей. Tesla Autopilot: point cloud из LiDAR - **выпуклая оболочка** - obstacle detection за 10ms. Convex hull - не академическая задача. Это production infrastructure.

**Graham Scan** - алгоритм построения выпуклой оболочки за O(n log n). Идея: выбрать нижнюю точку, отсортировать остальные по полярному углу, обходить с использованием стека для удаления «правых поворотов». Ronald Graham, 1972.

Почему третий этап O(n), а не O(n^2)? Каждая точка добавляется в стек ровно один раз и удаляется максимум один раз. Суммарно - не более 2n операций. Это amortized analysis в действии.

Jarvis March (Gift Wrapping)

Graham Scan сортирует всё заранее - O(n log n) даже если на hull всего 3 точки. Jarvis March (1973) подходит иначе: **заворачивает подарок**. Берёт крайнюю точку, натягивает ленту и поворачивает, пока не коснётся следующей. Никакой предварительной сортировки.

**Jarvis March** - алгоритм O(nh), где n - число точек, h - число вершин на hull. На каждом шаге находит точку с минимальным полярным углом относительно текущего направления. Output-sensitive: при малом h значительно быстрее Graham Scan.

Каждый шаг - O(n) (перебор всех точек для нахождения следующей). Шагов - h (число вершин hull). Итого: **O(nh)**.

Jarvis March выигрывает когда h << n. Именно такой случай у Tesla: облако из 100K точек LiDAR, из которых только 10-20 точек составляют выпуклую оболочку препятствия. В худшем случае деградирует до O(n^2). Можно ли объединить лучшее от обоих алгоритмов?

Chan's Algorithm

1996 год. Тимоти Чан - аспирант в Waterloo. Лаконичный вопрос: что если Graham Scan и Jarvis March не конкуренты, а **части одного решения**? Graham строит мини-hulls быстро. Jarvis идёт по ним. Бинарный поиск внутри каждого мини-hull заменяет полный перебор. Результат - O(n log h). Доказанно оптимально.

**Chan's Algorithm** - оптимальный output-sensitive алгоритм O(n log h). Идея: разбить n точек на группы по m, построить hull каждой группы Graham Scan за O(m log m), затем объединить hulls через Jarvis March где поиск следующей точки - бинарный поиск по каждому мини-hull за O(log m).

O(n log h) - **доказанно оптимально** в модели сравнений. Трюк с угадыванием m через двойную экспоненту 2^(2^t) добавляет лишь константу к общей стоимости. Удвоение (2, 4, 8...) не даёт O(n log h) - при O(log h) неудачных попытках суммарная работа становится O(n log h * log h).

Incremental Convex Hull

Предыдущие алгоритмы - offline: нужен весь набор точек. Но GPS-трек автомобиля или LiDAR-скан это **поток данных**: точки приходят одна за другой. Нужен online-алгоритм, обновляющий hull при добавлении каждой точки без перестройки с нуля.

**Incremental Convex Hull** - online-алгоритм. При добавлении точки p: если p внутри текущего hull - ничего не делаем. Если снаружи - находим две касательные из p к hull и обновляем оболочку. С balanced BST: O(log h) amortized.

С balanced BST (std::set в C++, SortedList в Python) каждая операция O(log h). Для n точек суммарно: **O(n log h)** - совпадает с оптимальным offline-алгоритмом Чана. Online-задача, offline-оптимальность.

Convex hull - одна из самых изученных задач в computer science. От простого Graham Scan (1972) до оптимального Chan's Algorithm (1996) - 24 года эволюции. Incremental версия показывает: offline-оптимальность достижима и в online-режиме.

Ключевые идеи

• **Graham Scan** O(n log n): сортировка по углу + стек с удалением правых поворотов
• **Jarvis March** O(nh): gift wrapping - на каждом шаге перебор всех n точек. Выигрывает при h << n
• **Chan's Algorithm** O(n log h): гибрид Graham + Jarvis. Мини-hulls + бинарный поиск. Доказанно оптимален
• **Incremental Hull** O(log h) amortized: online-алгоритм для потока точек, достигает offline-оптимума
• **Нижняя граница** Omega(n log h) - Chan's Algorithm достигает её. Лучше невозможно в модели сравнений
• **Tesla/GPU:** в production h << n почти всегда - поэтому Jarvis и Chan предпочтительнее Graham

Связанные темы

Convex hull - базовая подзадача для множества геометрических алгоритмов:

• Точки, отрезки, полигоны — Базовые примитивы и orientation-тест - основа всех hull-алгоритмов
• Пересечения отрезков — Sweep line - схожая парадигма обработки геометрических событий по порядку
• Divide and Conquer — D&C hull: разделить, построить рекурсивно, объединить через касательные

Вопросы для размышления

• Почему Graham Scan не является output-sensitive, хотя третий этап (обход со стеком) - O(n), а не O(n log n)?
• Можно ли адаптировать Chan's Algorithm для 3D convex hull? Какие сложности возникнут?
• В каких production-сценариях incremental hull предпочтительнее offline-алгоритмов?

Связанные уроки

• cgeom-01 — Базовые примитивы и orientation test - основа всех hull-алгоритмов
• cgeom-03 — Sweep line - схожая парадигма обработки геометрических событий
• alg-19-divide-conquer — D&C-версия convex hull: разделить, построить рекурсивно, объединить через касательные
• alg-10-binary-search — Бинарный поиск - ключевая операция в Chan's Algorithm и incremental hull
• alg-05-merge-sort — O(n log n) сортировка - первый шаг Graham Scan
• aie-09-embeddings — Convex hull кластеров embeddings - визуализация semantic spaces
• alg-20-greedy