AlgoScope

Graham Scan

Sort points by angle around the lowest point. Keep a stack, popping on right turns.

Computational geometry, algorithm, advanced
Pivot B.ABCDEFGH
Pivot B.ABCDEFGH

Plane Geometry: Graham scan: sort by angle, keep left turns

Decision, step 2 of 12

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.

How plane geometry works

Cost

Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)

Taught by the same lesson

Plane Geometry covers these too, in the same run.