What Are Convex Hulls?

Convex hulls are the smallest convex sets that contain a given set of points. For a finite point set in the plane, the hull is the polygon a rubber band would form if stretched around every point and released. Formally, the convex hull of a set S is the intersection of all convex sets containing S, and equivalently the set of all convex combinations of points in S. The idea belongs to convex geometry and convex analysis, where it supplies the link between a set and the convex functions defined over it, and it became a working computational object with the growth of computational geometry in the 1970s.

Two classical results bound how much information a hull really carries. Caratheodory's theorem says that in d dimensions every point of the hull can be written as a convex combination of at most d + 1 points of S, so the representation never needs more than a handful of vertices per point. The upper bound theorem limits the number of faces of a hull of n points in d dimensions, which is what makes exact hull computation tractable in low dimensions and expensive in high ones.

Representations and Basic Properties

A convex hull can be described in two dual ways: as the convex combination of a vertex set, called the V-representation, or as the intersection of a finite family of half-spaces, called the H-representation. Converting between them is the vertex enumeration and facet enumeration problem, and the cost of that conversion drives much of the practical difficulty in linear programming and polyhedral computation. Points of S that lie strictly inside the hull are called nonextreme and contribute nothing to either representation, so identifying and discarding them early is a common optimization. The construction also carries over from sets to functions: the convex envelope of a function, meaning the largest convex function that stays below it, is the function whose epigraph is the convex hull of the original epigraph. That is why hull operations appear whenever a nonconvex objective is replaced by a convex relaxation.

Algorithms in the Plane and in Higher Dimensions

In two dimensions the hull of n points can be built in O(n log n) time by the Graham scan, which sorts points by polar angle and then walks the sequence removing right turns, or by Andrew's monotone chain variant that sorts by coordinate instead. Sorting reduces to hull construction, so O(n log n) is optimal for comparison-based algorithms on arbitrary inputs. Output-sensitive methods do better when the hull is small: the gift wrapping method of Jarvis runs in O(nh) time for h hull vertices, and Chan's algorithm attains O(n log h). For general dimension the standard workhorse is Quickhull, described in the 1996 paper The Quickhull Algorithm for Convex Hulls, which merges the two-dimensional divide-and-conquer scheme with the beneath-beyond method and is distributed as the Qhull library. Randomized construction remains an active subject, including recent work on output-sensitive randomized variants of Quickhull.

Connections to Triangulation and Optimization

Lifting a planar point set onto the paraboloid z equal to x squared plus y squared turns the lower hull of the lifted points into the Delaunay triangulation of the original set, so one hull routine serves both problems, and the same lifting yields Voronoi diagrams by duality. In mathematical programming, the convex hull of the feasible integer points of a mixed-integer program is the polyhedron whose linear relaxation would be exact, and cutting-plane methods are attempts to approximate it one inequality at a time. Convex hulls also define the feasible sets in support vector machine training, where the maximum-margin separator is determined by the closest points of two hulls.

Applications

Convex hulls have applications in a wide range of fields, including:

• Collision detection and physics simulation in robotics and computer graphics
• Geographic information systems, where hulls bound spatial data sets
• Pattern recognition and outlier detection in machine learning
• Mesh generation through Delaunay triangulation
• Integer programming and combinatorial optimization
• Image analysis, including shape descriptors and convexity defects