Convex Hull · aiwiki.page

The convex hull of a set of points is the smallest convex set containing them. In Euclidean space, convexity means that the entire line segment between any two points of a set also belongs to the set. For a finite collection of points in the plane, the convex hull can be visualized as the region enclosed by a taut rubber band stretched around the outermost points. The hull includes the enclosed region, not merely its boundary. (cs.princeton.edu)

Definition and mathematical representation

Let $S$ be a subset of a real vector space. Its convex hull, written $\operatorname{conv}(S)$ , is

\operatorname{conv}(S) = \left\{ \sum_{i=1}^{m}\lambda_i x_i \;\middle|\; m\geq 1,\; x_i\in S,\; \lambda_i\geq 0,\; \sum_{i=1}^{m}\lambda_i=1 \right\}.

Each expression in this definition is a convex combination: a weighted average whose weights are nonnegative and sum to one. Only finite combinations are required, even when $S$ is infinite. Equivalently,

\operatorname{conv}(S) = \bigcap_{\substack{C\supseteq S\\ C\text{ convex}}}C.

Thus “smallest” refers to containment: every convex set containing $S$ also contains $\operatorname{conv}(S)$ . (stanford.edu)

For a finite set $S=\{p_1,\ldots,p_n\}\subseteq\mathbb R^d$ , place the points in the columns of a matrix $P$ . Membership in the hull can then be expressed as

x=P\lambda,\qquad \lambda_i\geq 0,\qquad \mathbf 1^{T}\lambda=1.

Consequently, testing whether a specified point belongs to a finite convex hull is a feasibility problem in linear programming. This follows directly from the convex-combination representation. (stanford.edu)

Geometry and finite point sets

A nonempty finite convex hull is a convex polytope, or equivalently a bounded polyhedron. Its dimension need not equal that of the ambient space: collinear points in three dimensions still produce a segment, while coplanar points produce a planar hull. (stanford.edu)

Typical examples include:

A single point, whose hull is that point.
Two distinct points, whose hull is their connecting segment.
Three noncollinear planar points, whose hull is the filled triangle they determine.
A finite noncollinear planar set, whose hull is a filled convex polygon.

For a finite planar set, an algorithm commonly represents the hull by listing its vertices in clockwise or counterclockwise order, rather than explicitly representing every point in the enclosed region. (ti.inf.ethz.ch)

An extreme point of a convex set is a point that cannot lie strictly between two distinct points of that set. The extreme points of a finite convex hull are its vertices. A boundary point lying in the middle of an edge is therefore not a vertex; software interfaces must distinguish between reporting extreme points and reporting every input point on the boundary. CGAL’s planar hull routines, for example, return the extreme points in counterclockwise order. (doc.cgal.org)

Carathéodory’s theorem and closure

Carathéodory’s theorem states that every point in the convex hull of a subset of $\mathbb R^d$ can be expressed as a convex combination of at most $d+1$ points of that subset. Thus three points suffice for any individual point in a planar hull, and four suffice in three-dimensional space. This does not mean that the entire hull has at most $d+1$ vertices: different points may require different subsets. The proof reduces a longer representation by exploiting dependence among the vectors $(x_i,1)$ , adjusting the coefficients until one becomes zero. (web.mit.edu)

Convex hulls also require care concerning closure. The hull of a compact subset of $\mathbb R^d$ is compact, but the hull of a closed set need not be closed. The closed convex hull is $\overline{\operatorname{conv}(S)}$ , which may contain additional limit points. These distinctions disappear for finite sets, whose hulls are compact. (web.mit.edu)

For a compact set, the convex hull is also the intersection of all closed half-spaces containing the set. Each half-space is bounded by a hyperplane and retains one side of it. This supplies a description through inequalities, complementary to the description through convex combinations. (ti.inf.ethz.ch)

Algorithms and historical development

Computing finite convex hulls is a central problem in computational geometry. For planar input, let $n$ denote the number of input points and $h$ the number of hull vertices. Algorithms differ in how they organize the points and whether their running time depends on the output size. (cs.jhu.edu)

Graham scan, introduced by Ronald Graham in 1972, first sorts points by their direction from an extreme point, then scans them while maintaining a candidate boundary. Points creating an inward turn are removed. Sorting takes $O(n\log n)$ time and the subsequent scan takes linear time. The method was an early optimal planar hull algorithm. (cs.princeton.edu)

Andrew’s monotone-chain algorithm sorts points lexicographically by coordinates, then builds lower and upper chains. Like Graham scan, it has $O(n\log n)$ running time, but avoids sorting by polar angle. (algs4.cs.princeton.edu)

Jarvis march, or gift wrapping, repeatedly selects the next supporting edge, examining the input points at each step. Its running time is $O(nh)$ , making it attractive when the hull has few vertices. Chan’s algorithm, published in 1996, combines hulls of smaller groups with wrapping to achieve $O(n\log h)$ time in two and three dimensions. This is an output-sensitive bound: the amount of work reflects the size of the answer as well as the input. (cs.jhu.edu)

In higher dimensions, the output includes facets and their adjacency relations, not just an ordered polygon. Qhull implements Quickhull-based construction for multidimensional hulls and related geometric structures. (qhull.org)

Orientation tests and numerical robustness

Planar hull algorithms commonly use an orientation test for three points $a,b,c$ :

D=(b_x-a_x)(c_y-a_y) -(b_y-a_y)(c_x-a_x).

This determinant is positive for a counterclockwise turn, negative for a clockwise turn, and zero for collinearity. It enables comparisons of directions without explicitly computing angles or trigonometric functions. (cs.princeton.edu)

With floating-point arithmetic, nearly collinear or coplanar points can produce unreliable signs because of rounding error. An incorrect geometric decision can corrupt the hull’s connectivity, producing inverted facets or inconsistent adjacency. Robust implementations may use exact predicates, merge nearly coplanar facets, or perturb the input slightly; these approaches have different implications for the output. Perturbation, in particular, computes a hull of modified coordinates rather than the exact original data. (qhull.org)

Repeated points and lower-dimensional input are additional implementation cases. An interface that expects a full-dimensional polyhedron cannot treat a segment or planar hull as an ordinary three-dimensional solid without special handling. CGAL’s planar routines explicitly accommodate empty, singleton, and segment hulls. (doc.cgal.org)

Applications and limitations

In mathematical optimization, hulls provide descriptions of feasible mixtures of finitely many alternatives. They also connect geometry with linear separability: two nonempty finite point classes can be strictly separated by a hyperplane exactly when their convex hulls are disjoint. The distance between the hulls appears in the geometric interpretation of maximum-margin classification and support vector machines. (stanford.edu)

Convex hulls are closely related to Delaunay triangulation. Lifting points from $\mathbb R^d$ onto the paraboloid

(x_1,\ldots,x_d) \longmapsto (x_1,\ldots,x_d,x_1^2+\cdots+x_d^2)

allows the Delaunay structure to be recovered from the lower convex hull in one additional dimension. Half-space intersection is likewise related to hull construction through polar duality. (qhull.org)

A hull deliberately discards nonconvex detail: it fills indentations and gaps and does not preserve the arrangement of interior points. It is therefore an enclosing representation, not a reconstruction of an arbitrary shape. Large dimensionality creates a separate representational difficulty. For example, the $d$ -dimensional cube needs only $2d$ defining inequalities but has $2^d$ vertices, so its inequality and vertex descriptions can differ exponentially in size. (cs.princeton.edu)

References

Convex Hullscs.princeton.edu
Convex Optimizationstanford.edu
Computational Geometry, CG 2012ti.inf.ethz.ch
Convex Analysis and Optimization Lecture Slidesweb.mit.edu
CGAL — 2D Convex Hulls and Extreme Points: User Manualdoc.cgal.org
ApproxDecompShapes.pdfcs.princeton.edu
Convex Hullalgs4.cs.princeton.edu
Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensionscs.jhu.edu