the convex hull

Hammer a nail into a board at each of your points, stretch a rubber band so it surrounds all the nails, and let it snap tight. The taut shape it settles into — touching only the outermost nails and skipping everyone tucked inside — is the convex hull. Formally, the convex hull of a set of points is the smallest convex polygon that contains every point: convex meaning no dents, so the boundary never turns back inward and any line segment between two points of the region stays inside it. The hull's corners are a subset of the original points; everything else lies on or within the boundary.

It is the most fundamental structure in computational geometry because it captures the outer shape of a point cloud and throws away the interior clutter. Once you have the hull you can quickly read off the diameter (the two farthest points), the smallest enclosing box, or whether a new point is inside the cloud. The hull is unique for a given set, and its vertices, listed in order around the boundary, make exactly the turns you expect: walk the boundary counterclockwise and you only ever turn left (or go straight). That very property — every boundary turn is a left turn — is what the hull algorithms exploit and verify using the orientation test.

Several algorithms compute it, and they trade off in instructive ways. Graham scan and Andrew's monotone chain both sort the points and run in O(n log n); gift wrapping (the Jarvis march) runs in O(n*h) where h is the number of hull vertices, which is great when the hull is small but can be O(n^2) when nearly all points are on the hull. No comparison-based method can beat O(n log n) in the worst case, because sorting reduces to hull-finding — that is the convex-hull lower bound. Convex hulls show up in collision detection, pattern recognition, computing shapes that bound data, and as a subroutine inside many other geometric algorithms.