Combinatorics • Topic 35

Convex Hull

The Convex Hull of a set of points is the smallest convex polygon (or polyhedron in higher dimensions) that contains all the points. It is like snapping a rubber band around the outermost points.

Definition

Definition (Convex Hull)

For a set of points

S

in the plane, the convex hull

C H (S)

is the intersection of all convex sets containing

S

. Alternatively, it is the set of all convex combinations of points in

S

C H (S) = {i = 1 \sum k α_{i} p_{i} ∣ p_{i} \in S, α_{i} \geq 0, \sum α_{i} = 1}

Properties

Vertices: The vertices of the convex hull are always a subset of the original point set $S$ .
Edges: An edge connects two points $p, q \in S$ if and only if all other points lie to one side of the line passing through $p$ and $q$ .

Algorithms (Brief Overview)

While primarily algorithmic, understanding how to construct hulls is useful for geometric proofs.

Graham Scan: Sort points by angle around a pivot, then iterate to remove "concave" turns.
Gift Wrapping (Jarvis March): Start at the leftmost point, find the point with the smallest angle relative to the current point, repeat.

Practice Problems

Exercise (Problem 1)

Given 5 points in a plane such that no three are collinear, prove that their convex hull is either a triangle, a quadrilateral, or a pentagon.

Exercise (Problem 2)

Prove that the perimeter of the convex hull of a set of points is less than or equal to the perimeter of any other polygon enclosing the set.

Exercise (Problem 3)

If a set of points

S

is symmetric about the origin, prove that its convex hull

C H (S)

is also symmetric about the origin.