the convex hull

Stretch a rubber band around a scattered handful of nails on a board: it snaps to the outermost nails and encloses everything in the smallest taut loop. The convex hull is the n-dimensional version of that rubber band. Given any set S of points, its convex hull conv(S) is the smallest convex set that contains S — the tightest convex skin you can shrink-wrap around the points. In the plane it is a convex polygon through the outer points; in space it is a convex polytope; for a smooth cloud it can be a curved convex body.

There are two equivalent definitions, one from outside and one from inside. From outside, conv(S) is the intersection of all convex sets containing S (intersecting convex sets keeps them convex, so this intersection is the smallest convex set containing S). From inside, conv(S) is the set of all convex combinations of points of S: all finite sums t_1*x_1 + ... + t_m*x_m where each x_i is in S, each t_i >= 0, and the weights sum to 1. A convex combination is just a weighted average, a center of mass with nonnegative weights, so the hull is everything you can reach as a balance point of finitely many sample points.

Convex hulls are everywhere: they define the feasible region of a linear program, the support of a probability distribution's mean, the Newton polytope of a polynomial, and the basic shape in computational geometry. Caratheodory's theorem sharpens the inside picture — in R^n you never need more than n + 1 points per convex combination — which is why hulls of finite sets are polytopes with finitely many vertices. A caution: the convex hull of a closed set need not be closed (think of a closed set whose points march off to infinity in a way that fills a half-plane only in the limit), so for unbounded S one often takes the closed convex hull, the closure of conv(S).