Convex Hull

Цели урока

• Understand Graham Scan: sort by angle, stack, right-turn removal
• Compare Graham Scan and Jarvis March based on the value of h
• Explain Chan's Algorithm and why 2^(2^t) is used instead of simple doubling
• Understand incremental hull for streaming data

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

• Points, Segments, Polygons

Google Maps: one route - Dijkstra on a graph with 50M+ nodes. Uber finds the nearest driver among thousands in 200 ms. Tesla Autopilot: LiDAR point cloud - convex hull - obstacle detection in 10 ms. Computational geometry is production infrastructure.

• **Tesla Autopilot:** LiDAR produces 100K points/sec, convex hull of obstacles is built in under 10 ms for collision avoidance
• **GJK Algorithm (game physics):** Unreal Engine, Unity - convex hull of each rigid body for collision detection
• **Computer vision:** bounding convex hull of a region of interest - YOLO, Mask R-CNN use it for object detection
• **GPS tracking:** Uber, Lyft - incremental hull for tracking driver coverage zones in real time
• **ML clustering:** visualizing cluster boundaries in sklearn - convex hull of each cluster in feature space
• **Robotics (Boston Dynamics):** path planning - convex hull of obstacles defines forbidden zones for the trajectory

Shamos, Hoey and the birth of computational geometry

In 1975, Michael Shamos and Dan Hoey published "Closest-point problems" - one of the first papers in the field they called "computational geometry". In 1985, Shamos co-authored with Franco Preparata the foundational textbook **"Computational Geometry: An Introduction"**, where convex hull took center stage. Before their work, geometric algorithms existed in isolation. They created the discipline.

Graham Scan

Google Maps: one route - Dijkstra on a graph with 50M+ nodes. Uber finds the nearest driver among thousands in 200 ms. Tesla Autopilot: LiDAR point cloud - **convex hull** - obstacle detection in 10 ms. Convex hull is not an academic exercise. It is production infrastructure.

**Graham Scan** builds the convex hull in O(n log n). The idea: pick the bottommost point, sort the rest by polar angle, then sweep with a stack that discards "right turns". Ronald Graham, 1972.

Why is step three O(n) and not O(n^2)? Each point is pushed onto the stack exactly once and popped at most once. In total - no more than 2n operations. Classic amortized analysis.

Jarvis March (Gift Wrapping)

Graham Scan sorts everything upfront - O(n log n) even when the hull has only 3 points. Jarvis March (1973) takes a different approach: **wrap a gift**. Grab the outermost point, pull the ribbon taut, rotate until the next point is touched. No upfront sorting.

**Jarvis March** runs in O(nh), where n is the number of points and h is the number of hull vertices. At each step, find the point with the smallest polar angle relative to the current direction. Output-sensitive: significantly faster than Graham Scan when h is small.

Each step takes O(n) - scanning all points to find the next hull vertex. There are h steps. Total: **O(nh)**.

Jarvis March wins when h << n. Exactly the Tesla case: 100K LiDAR points, only 10-20 form the hull of an obstacle. In the worst case it degrades to O(n^2). Can the best of both algorithms be combined?

Chan's Algorithm

1996. Timothy Chan, graduate student at Waterloo. A compact question: what if Graham Scan and Jarvis March are not rivals, but **parts of a single solution**? Graham builds mini-hulls fast. Jarvis traverses them. Binary search inside each mini-hull replaces the full scan. Result: O(n log h). Provably optimal.

**Chan's Algorithm** is an optimal output-sensitive algorithm running in O(n log h). The idea: partition n points into groups of m, build a hull for each group with Graham Scan in O(m log m), then merge the hulls using Jarvis March where finding the next point uses binary search over each mini-hull in O(log m).

O(n log h) is **provably optimal** in the comparison model. The trick of guessing m via the double exponential 2^(2^t) adds only a constant factor. Simple doubling (2, 4, 8...) does not give O(n log h) - with O(log h) failed trials the total work becomes O(n log h * log h).

Incremental Convex Hull

The previous algorithms are offline: the full point set must be known upfront. But a car GPS track or a LiDAR scan is a **data stream**: points arrive one at a time. An online algorithm is needed - one that updates the hull on each new point without rebuilding from scratch.

**Incremental Convex Hull** is an online algorithm. When point p is added: if p is inside the current hull - do nothing. If outside - find two tangents from p to the hull and update. With a balanced BST: O(log h) amortized per point.

With a balanced BST (`std::set` in C++, `SortedList` in Python) each operation runs in O(log h). For n points in total: **O(n log h)** - matching the optimal offline algorithm Chan's Algorithm. Online problem, offline optimality.

Convex hull is one of the most studied problems in computer science. From simple Graham Scan (1972) to the optimal Chan's Algorithm (1996) - 24 years of evolution. The incremental version shows that offline optimality is achievable in the online setting.

Key Takeaways

• **Graham Scan** O(n log n): sort by angle + stack with right-turn removal
• **Jarvis March** O(nh): gift wrapping - scan all n points at each step. Wins when h << n
• **Chan's Algorithm** O(n log h): Graham + Jarvis hybrid. Mini-hulls + binary search. Provably optimal
• **Incremental Hull** O(log h) amortized: online algorithm for a point stream, achieves offline optimum
• **Lower bound** Omega(n log h) - Chan's Algorithm achieves it. Nothing better is possible in the comparison model
• **Tesla/production:** in practice h << n almost always - Jarvis and Chan are preferred over Graham

Related Topics

Convex hull is a fundamental sub-problem for many geometric algorithms:

• Points, Segments, Polygons — Basic primitives and the orientation test - the foundation of all hull algorithms
• Segment Intersections — Sweep line - a similar paradigm of processing geometric events in order
• Divide and Conquer — D&C hull: split, build recursively, merge via tangents

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

• Why is Graham Scan not output-sensitive, even though the stack sweep (step 3) runs in O(n)?
• Could Chan's Algorithm be adapted for 3D convex hull? What challenges would arise?
• In which production scenarios is the incremental hull preferable to offline algorithms?

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

• cgeom-01 — Basic primitives and orientation test are the foundation of all hull algorithms
• cgeom-03 — Sweep line - a similar paradigm for processing geometric events in order
• alg-19-divide-conquer — D&C convex hull: split, build recursively, merge via tangents
• alg-10-binary-search — Binary search is the key operation in Chan's Algorithm and incremental hull
• alg-05-merge-sort — O(n log n) sort is the first step of Graham Scan
• aie-09-embeddings — Convex hull of embedding clusters - visualization of semantic spaces
• alg-20-greedy