Convex Hull — Definition, Formula & Examples

The convex hull of a set of points is the smallest convex shape that contains all the points. You can picture it as the shape formed by stretching a rubber band around the outermost points and letting it snap tight.

Given a set $S \subseteq \mathbb{R}^n$ , the convex hull $\operatorname{conv}(S)$ is the intersection of all convex sets containing $S$ . Equivalently, it is the set of all convex combinations of points in $S$ : $\operatorname{conv}(S) = \left\{ \sum_{i=1}^{k} \lambda_i \mathbf{x}_i \;\middle|\; \mathbf{x}_i \in S,\; \lambda_i \geq 0,\; \sum_{i=1}^{k} \lambda_i = 1 \right\}$ .

Key Formula

\operatorname{conv}(S) = \left\{ \sum_{i=1}^{k} \lambda_i \mathbf{x}_i \;\middle|\; \mathbf{x}_i \in S,\; \lambda_i \geq 0,\; \sum_{i=1}^{k} \lambda_i = 1 \right\}

Where:

$S$ = The original set of points
$\mathbf{x}_i$ = Points chosen from S
$\lambda_i$ = Non-negative weights that sum to 1
$k$ = Number of points in the convex combination

How It Works

To find the convex hull of a finite set of points in 2D, identify which points lie on the outer boundary — these are the vertices of the hull. Interior points are enclosed but do not contribute to the hull's shape. Algorithmically, methods like the gift-wrapping algorithm or Graham scan systematically determine these boundary points. In higher dimensions, the same idea applies: the hull is a convex polytope whose vertices are a subset of the original points.

Worked Example

Problem: Find the convex hull of the points

A = (0,0)

B = (4,0)

C = (2,3)

D = (2,1)

\mathbb{R}^2

Step 1: Plot or inspect the points. Identify candidates for the outer boundary by checking which points are not interior to any triangle formed by the others.

Step 2: Check whether

D = (2,1)

lies inside the triangle

ABC

. Express

D

as a convex combination of

A

B

C

: solve

2 = 4\lambda_2 + 2\lambda_3

and

1 = 3\lambda_3

with

\lambda_1 + \lambda_2 + \lambda_3 = 1

. This gives

\lambda_3 = \frac{1}{3}

\lambda_2 = \frac{1}{3}

\lambda_1 = \frac{1}{3}

. All weights are positive, so

D

is inside triangle

ABC

D = \tfrac{1}{3}A + \tfrac{1}{3}B + \tfrac{1}{3}C

Step 3: Since

D

is interior, the convex hull is the triangle with vertices

A

B

, and

C

Answer: The convex hull is triangle

ABC

with vertices

(0,0)

(4,0)

, and

(2,3)

Why It Matters

Convex hulls appear in computational geometry algorithms, collision detection in computer graphics, and linear programming where feasible regions are convex polytopes. In machine learning, support vector machines rely on the geometry of convex hulls to separate classes of data points.

Common Mistakes

Mistake: Including interior points as vertices of the convex hull.

Correction: Only points on the boundary of the hull are its vertices. Test whether a candidate point can be written as a convex combination of other points; if so, it is interior and not a vertex.