Why the Convex Hull is the Set of All Non-Negative Weighted Averages

Ever wondered how game engines detect collisions between two complex bodies? Calculating a perfect collision between highly detailed shapes would be nearly impossible to run in real time. Instead, game engines simplify the math by approximating those bodies with their convex hulls—effectively creating the "tightest possible wrapping" around the object to keep the game running fast. If we take the simplest example: where our object is just a set of three points, then its convex hull becomes the solid triangle that has those points as its corners.

To understand what a convex hull is, we first have to understand what makes a set convex. A convex set is a collection of points where, if you pick any two points inside the set and draw a straight line segment between them, that entire line segment stays completely inside the set. If even a tiny piece of the line crosses outside the boundary, the set is not convex (it is concave).

The Line Test

Mathematically, a set is convex if for any two points $ x $ and $ y $ inside it, and any fraction $ \lambda $ between 0 and 1, the point given by: $ (1 - \lambda)x + \lambda y $ is also in that set. That formula is just the algebraic way of describing every single point along the straight line connecting $ x $ and $ y $. As you slide $ \lambda $ from 0 to 1, you travel smoothly from point $ x $ to point $ y $.

For given set of points $S$ we can define the convex hull $H$ as the smallest convex set containing $S$ . The convex hull of a set of points is the set of all possible convex combinations (weighted averages) of those points. Yes I did say it and never proved it, but I will do it in a moment, just let me put it down first. $$ \left\{ \sum_{i=1}^k \alpha_i x_i \;\middle|\; x_i \in S, \, \alpha_i \geq 0, \, \sum_{i=1}^k \alpha_i = 1 \right\} $$

Let $ S = \{x_1, x_2, \dots, x_n\} $ be our finite set of points.

Let $H$ be the smallest convex set containing $S$ (the geometric hull).

Let $C$ be the set of all convex combinations of the points in $S$.

We want to prove that $H = C$.

In mathematics, to prove two sets $H$ and $C$ are equal ($H = C$), we must prove two things:

1. $C \subseteq H$ (Every convex combination is inside the smallest convex set).
2. $H \subseteq C$ (The smallest convex set is entirely contained within the set of convex combinations).

Part 1: Proving $C \subseteq H$ (Every combination is inside the hull)

We know that $H$ is a convex set, and it contains all the original points $\{x_1, \dots, x_n\}$. By the very definition of a convex set, if it contains two points, it must contain the line segment between them (which is a convex combination of 2 points).

We can extend this to $n$ points using mathematical induction:

• Base Case: For 2 points, if $x_1, x_2 \in H$, then by the definition of a convex set, $\alpha_1 x_1 + \alpha_2 x_2 \in H$ (where $\alpha_1 + \alpha_2 = 1, \alpha_i \geq 0$).

• Inductive Step: Assume that $H$ contains all convex combinations of $k$ points. Now consider a combination of $k+1$ points:

  $$x = \alpha_1 x_1 + \dots + \alpha_k x_k + \alpha_{k+1} x_{k+1}$$ If $\alpha_{k+1} < 1$, we can group the first $k$ terms by factoring out $(1 - \alpha_{k+1})$: $$x = (1 - \alpha_{k+1})y + \alpha_{k+1} x_{k+1}$$

where $$ y = \sum_{i=1}^k \frac{\alpha_i}{1 - \alpha_{k+1}} x_i $$

The term $y$ is a convex combination of $k$ points (since the new weights add up to 1). By our inductive assumption, $y \in H$.

Now, look at the whole equation: $x = (1 - \alpha_{k+1})y + \alpha_{k+1} x_{k+1}$. This is just a basic 2-point convex combination between $y$ and $x_{k+1}$. Since both $y$ and $x_{k+1}$ are in $H$, and $H$ is convex, $x$ must also be in $H$.

Therefore, every possible convex combination is trapped inside the geometric hull ($C \subseteq H$).

Part 2: Proving $H \subseteq C$ (The hull is contained in the combinations)

Remember, $H$ is defined as the smallest convex set containing $S$. If we can prove that the algebraic set $C$ is itself a convex set that contains $S$, then $H$ (being the absolute smallest) must be a subset of $C$, or at most equal to it.

1. Does $C$ contain $S$? Yes. To get the point $x_1$, just set $\alpha_1 = 1$ and all other $\alpha_i = 0$. This is a valid convex combination, so $S \subseteq C$.

2. Is $C$ convex? Let's test it using the line test. Take two arbitrary points $u$ and $v$ from $C$. Because they are in $C$, they can be written as convex combinations of the points in $S$:

   $$u = \sum \beta_i x_i \quad \text{and} \quad v = \sum \gamma_i x_i$$

   Now, take any point $w$ on the line segment between $u$ and $v$ using a fraction $\lambda \in [0, 1]$:

   $$w = \lambda u + (1 - \lambda) v$$

   Substitute the combinations for $u$ and $v$:

   $w = \lambda \left( \sum \beta_i x_i \right) + (1 - \lambda) \left( \sum \gamma_i x_i \right)$

   Group the terms by $x_i$:

   $$w = \sum \underbrace{\left[ \lambda \beta_i + (1 - \lambda)\gamma_i \right]}_{\text{New weights } \delta_i} x_i$$

Are these new weights $\delta_i$ valid?

• Since $\lambda, \beta_i, \gamma_i \geq 0$, then $\delta_i \geq 0$.
• If you sum all $\delta_i$, they expand to $\lambda(1) + (1-\lambda)(1) = 1$.

Because $w$ is written perfectly as a convex combination of $S$, $w$ belongs to $C$. This means $C$ is a convex set.

Conclusion

Since $C$ is a convex set that contains $S$, and $H$ is the smallest convex set that contains $S$, it is logically impossible for

$H$ to be larger than $C$. Therefore, $H \subseteq C$.

Combined with Part 1 ($C \subseteq H$), the two sets must be exactly identical: $H = C$. $\blacksquare$