AlgoScope

Monotone Chain

Sort by x, then build the lower and upper chains, popping while the turn is not a left turn.

Computational geometry, algorithm, advancedAlso called Andrew's algorithm
Pop H.ABCDEFGH
Pop H.ABCDEFGH

Plane Geometry: Monotone chain hull

Decision, step 4 of 26

lower hull: A, H, B is not a left turn (right turn), so H cannot be on the hull between them. Pop it.

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.