Graham Scan
Sort points by angle around the lowest point. Keep a stack, popping on right turns.
Plane Geometry: Graham scan: sort by angle, keep left turns
The pivot is B (7, 1), the lowest point. It is certainly on the hull, and every other point is now ordered by the angle it makes from here: C, D, H, G, E, F, A.
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.