# Convex Hull - Graham's scan = $O(n\lg n)$ - When scanning through the points, the segments eliminated formed [[triangulation]] of the graph. - From left to right, the upper hull makes non-left turn, vice versa for lower hull. - If an incorrect turn is made, go back a point and eliminate it from the hull. - If still making an incorrect turn, go back one more point. - Jarvis's march = $O(nh)$, where $h = o(\lg n)$ - Pick leftmost endpoint, which is guaranteed to be on the hull. - Use [[sweeping|sweep line]] to find the following highest/lowest endpoints. They are on the hull as well. - As if "wrapping a gift". - Merging convex hulls - [An efficient way of merging two convex hulls | Algorithm Tutor](https://algorithmtutor.com/Computational-Geometry/An-efficient-way-of-merging-two-convex-hull/) - [Divide and Conquer (Splitting) | UIUC CS](https://jeffe.cs.illinois.edu/teaching/compgeom/notes/14-convexhull.pdf)