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 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
  • Divide and Conquer (Splitting) | UIUC CS