Convex hull

What is a convex hull?

The convex hull of a set of points is the smallest convex polygon that contains all the points. Think of it as the shape you get when you stretch a rubber band around the outermost points and let it snap tight. Every point is either on the hull boundary or inside it, and every line segment between two hull points lies entirely within the hull.

Gift wrapping (Jarvis march)

Start from the leftmost point. At each step, find the point that makes the smallest counterclockwise angle from the current direction. Wrap around the hull one edge at a time. The time complexity is O(nh) where n is the total number of points and h is the number of hull vertices. When h is small, this is efficient; when most points are on the hull, it degrades to O(n²).

Graham scan

Sort all points by polar angle around the lowest point. Then process points in order, maintaining a stack. At each step, check whether the new point makes a left turn or right turn with the last two points on the stack. Right turns mean the middle point is inside the hull and gets popped. The sort dominates at O(n log n), and the scan itself is linear.

Quickhull

Find the leftmost and rightmost points, which must be on the hull. These divide the points into upper and lower sets. For each set, find the point farthest from the dividing line — it must also be on the hull. Recurse on the resulting subsets. Like quicksort, it is O(n log n) on average but can degrade to O(n²) in the worst case. In practice, it is often the fastest algorithm for random point distributions.

Applications

Convex hulls appear in collision detection (game physics), geographic information systems (bounding regions), image processing (object detection), statistics (enclosing data sets), and computational geometry (as a building block for more complex algorithms like Delaunay triangulation and Voronoi diagrams). The problem is one of the foundational problems in computational geometry, with an Ω(n log n) lower bound proved by reduction from sorting.