Convex hull

The convex hull of a set of points in a plane is the smallest convex polygon that contains every point. It is to computational geometry what sorting is to general algorithmics: the simplest nontrivial problem that exposes the structure of the domain. The hull's vertices are a subset of the original points, and its edges form the boundary of the minimal enclosing convex shape.

The problem has been solved optimally in O(n log n) time for the planar case, and the lower bound is tight: sorting reduces to convex hull, so any hull algorithm faster than n log n would imply a faster sort. In higher dimensions, the problem explodes combinatorially: the convex hull of n points in d dimensions can have Ω(n^⌊d/2⌋) facets, making the output size itself exponential in dimension. This is why convex hull algorithms in dimensions above three are rarely used in practice, and why approximate hulls and bounding volume hierarchies dominate in applications like collision detection and computer graphics.

The relationship between convex hulls and Delaunay triangulations is intimate: the Delaunay triangulation of a point set in the plane can be computed by projecting the points onto a paraboloid in three dimensions and computing the lower convex hull. This reduction — from a seemingly complex meshing problem to a hull computation — is one of the most elegant connections in geometric algorithms. The dual relationship, between hulls and Voronoi diagrams, further demonstrates that convex hulls are not merely a problem but a lens through which other geometric structures become visible.