AlgoScope

Convex Hull

The smallest convex polygon containing all points, built by monotone chain from sorted points.

Computational geometry, analysis, intermediate
Hull with 6 points.ABCDEFGH
Hull with 6 points.ABCDEFGH

Plane Geometry: Monotone chain hull

Result, step 26 of 26

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).

How plane geometry works

Cost

Space
O(n)

Leads to

Topics that need this one first.

Taught by the same lesson

Plane Geometry covers these too, in the same run.