Convex Hull
The smallest convex polygon containing all points, built by monotone chain from sorted points.
Plane Geometry: Monotone chain hull
Hull: A, B, E, F, G, H, 6 of 8 points, listed counter-clockwise. Sorting costs O(n log n) and each point is pushed and popped at most twice, so the chains take O(n).
Cost
- Space
- O(n)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Plane Geometry covers these too, in the same run.