Convex Hull
The smallest convex polygon containing all points, built by monotone chain from sorted points.
Decision · step 4 of 26Plane 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.
What you will see
A rubber band snapping around the point set.
Cost
| Space | O(n) |
|---|
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Points announce coordinates and role; each step announces the geometric test and its result in words (left turn, intersects).
Reduced motion: Shapes appear in place; the sweep line jumps between events.
Before this
Related
Taught by the same lesson
Plane Geometry covers these too, in the same run.