Algebraic, Discrete & Computational Geometry and Frontiers

a convex hull

Hammer a handful of nails into a board at random spots, then stretch a rubber band so it surrounds all of them and let it snap tight. The taut band traces out a polygon hugging the outermost nails, with all the others tucked inside. That snapped-tight shape is the convex hull of the points: the smallest convex set that contains them all. It is the most economical 'wrapping' you can put around a set of points without any dents.

Said precisely, the convex hull of a set S is the intersection of every convex set that contains S — and since intersections of convex sets are convex, this really is the smallest convex set holding S. There is an equally useful constructive picture: the convex hull is the set of all 'weighted averages' of points of S, that is, all combinations t_1 P_1 + t_2 P_2 + ... + t_k P_k where the weights t_i are non-negative and add up to 1 (these are called convex combinations). For a finite set of points in the plane, the hull is a convex polygon whose corners (vertices) are some of the original points — exactly the rubber-band nails — and every other point lies inside or on an edge. The points that end up as corners are precisely those that cannot be written as an average of the others.

Computing the convex hull is a foundational task in computational geometry, solvable for n points in the plane in time proportional to n log n (the cost of sorting), by classic algorithms such as Graham scan and the gift-wrapping (Jarvis march) method. It is the first step in countless pipelines: collision detection, pattern recognition, finding the most extreme data points, and shape analysis. A frequent confusion is between the hull as a BOUNDARY (the polygon's outline) and the hull as a FILLED region (the solid inside); both usages exist, so it pays to say which you mean. Also note the hull throws away all interior structure — it tells you the outline only, never how the points are clustered within.

Take five points: four at the corners of a square and one dead center. The convex hull is just the square — its four corners are the vertices, and the center point is interior, contributing nothing to the outline. Adding a hundred more points scattered inside the square would still leave the hull unchanged: only the extreme points, the ones no average can reach, become corners.

Interior points are invisible to the hull; only the extreme points shape the outline.

The convex hull keeps only the outer silhouette. Two completely different point clouds can share the very same hull, so the hull alone tells you nothing about density, clustering, or anything happening in the interior.

Also called
convex enveloperubber-band shape凸殼