Monotone Chain
Sort by x, then build the lower and upper chains, popping while the turn is not a left turn.
Plane Geometry: Monotone chain hull
lower hull: A, H, B is not a left turn (right turn), so H cannot be on the hull between them. Pop it.
Cost
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Space
- O(n)
Before this
Related
Taught by the same lesson
Plane Geometry covers these too, in the same run.