Convex Hull

1. Intuitive Idea

The convex hull of a set of points is the smallest convex set that contains all those points.

🔹 Intuition:
Imagine driving nails at given points on a board and stretching a rubber band around them.
When released, the rubber band forms the convex hull.

---

2. Formal Definition

Let $S \subseteq \mathbb{R}^n$ be any set.

The convex hull of $S$, denoted by

$$\operatorname{conv}(S),$$

is defined as the set of all convex combinations of points in $S$.

That is,

$$\boxed{ \operatorname{conv}(S) = \left\{ \sum_{i=1}^k \lambda_i x_i \;\middle|\; x_i \in S,\; \lambda_i \ge 0,\; \sum_{i=1}^k \lambda_i = 1,\; k \in \mathbb{N} \right\} }$$

---

3. Convex Combination (Key Concept)

A convex combination of points $x_1, x_2, \dots, x_k$ is a weighted average:

$$\lambda_1 x_1 + \lambda_2 x_2 + \cdots + \lambda_k x_k$$

where:

• $\lambda_i \ge 0$
  

• $\sum \lambda_i = 1$
  

📌 Convex combinations fill in all points between the given points.

---

4. Alternative Characterization

The convex hull of a set $S$ is:

The intersection of all convex sets that contain $S$.

This shows:

• Existence

• Uniqueness

• Minimality

---

5. Simple Examples

Example 1: Two Points in $\mathbb{R}^2$

Let

$$S = \{x_1, x_2\}.$$

Then

$$\operatorname{conv}(S) = \{ \lambda x_1 + (1-\lambda)x_2 : \lambda \in [0,1] \},$$

which is the line segment joining $x_1$ and $x_2$.

---

Example 2: Three Non-Collinear Points

If $S = \{x_1, x_2, x_3\}$, then:

• The convex hull is a filled triangle

• Includes the interior, not just the edges

---

Example 3: Vertices of a Square

The convex hull of the four vertices is the entire square, including its interior.

6. Important Properties of Convex Hulls

(i) Convexity

$$\operatorname{conv}(S) \text{ is always convex.}$$

---

(ii) Minimality

If $C$ is any convex set containing $S$, then

$$\operatorname{conv}(S) \subseteq C.$$

---

(iii) Idempotence

$$\operatorname{conv}(\operatorname{conv}(S)) = \operatorname{conv}(S).$$

---

(iv) Finite Representation (Carathéodory’s Theorem)

In $\mathbb{R}^n$, any point in the convex hull of $S$ can be written as a convex combination of at most $n+1$ points from $S$.

---

7. Extreme Points and Convex Hull

• Extreme points are points that cannot be written as convex combinations of others.

• The convex hull is completely determined by its extreme points.

📌 In polygons and polyhedra:

• Extreme points = vertices

---

8. Convex Hull in Machine Learning

(i) Classification

• Linear classifiers separate convex hulls of data classes

(ii) Support Vector Machines

• Decision boundary depends on extreme points (support vectors)

(iii) Clustering

• Convex hulls help detect outliers

---

9. Convex Hull vs Convex Set

Aspect	Convex Set	Convex Hull
Meaning	Already convex	Smallest convex set containing a given set
Construction	Given directly	Built using convex combinations
Example	Disk, cube	Hull of scattered points