2

I know that the following definitions of convex hull are equivalent:

$\textbf{Definition 1: }$The convex hull of $k$ points in $\mathbb{R^n}$ is the smallest convex set containting the $k$ points.

$\textbf{Definition 2: }$The convex hull of $k$ points in $\mathbb{R^n}$ is the set $C$ of all convex combinations of the $k$ points.

Here we take convex combination to be a linear combination $c_1 a_1 + \ldots + c_k a_k$ where $c_i \geq 0$ and $\sum c_i =1$ Could someone geometrically explain why the restrictions on $c_i$ force $C$ to be the convex hull of the $k$ points. For just two points it is clear to me but for the case of three points or more I find it hard to grasp intuitively. Why do these algebraic constraints on the coefficients of the combinations produce figures like triangles, squares, tetrahedrons, etc.

Thanks.

1729
  • 2,157
  • Work geometrically. For a pair of points, the convex hull is the segment joining the two points. For three points, the convex hull is the triangle formed by the three points. Etc, etc. – copper.hat Dec 28 '17 at 00:23
  • Working in finite dimensions is special in the same way that any point in $n$ dimensional space can be written in terms of $n$ basis vectors. It turns out that (in $n$ dimensions) that any point in the convex hull can be written as a convex combination of at most $n+1$ points (Carathéodory's theorem). – copper.hat Dec 28 '17 at 00:25
  • A 'recursive' way to think of it is that the convex hull of $k$ points is the convex hull of one of the points and the convex hull of the remaining points. – copper.hat Dec 28 '17 at 00:28
  • You can consider $c_i$ the $k$-linear coordinates for the shape defined by the vertices $a_i$. Analogous to trilinear coordinates for a triangle, points $0 \le c_i \le 1$, $\sum_{i=1}^k c_i = 1$ cover the convex set containing the $k$ points at least once. (That is, there may be different $k$-linear coordinates that refer to the same point; but every point within the convex set is covered, and only the convex set is covered.) Uh, I hope I didn't just muddle the waters more.. :) I recommend exploring this through interactive graphics. – Nominal Animal Dec 28 '17 at 05:32

1 Answers1

2

For just two points it is clear to me

Think iteratively (assuming $c_j \lt 1$ for the sake of the following argument, which doesn't lose generality since cases where one of the $c_j=1$ correspond to actual points in the given set, which are known to be included in the convex hull anyway): $$\;\displaystyle a =c_1 a_1 + \ldots + c_k a_k = c_1 a_1 + (1-c_1) \left(\frac{c_2}{1-c_1}a_2+ \cdots + \frac{c_k}{1-c_1}a_k\right)=c_1 a_1+(1-c_1)a'$$

Therefore $a$ is on the segment between $a_1$ and $a'$ where $\displaystyle a'=\frac{c_2}{1-c_1}a_2+ \cdots + \frac{c_k}{1-c_1}a_k\,$. Note that $\displaystyle \frac{c_j}{1-c_1} \ge 0$ and $\displaystyle \sum_{j=2}^k \frac{c_j}{1-c_1}=1\,$, so $a'$ is a convex combination of the $k-1$ points $a_2, \cdots,a_k$. Repeat the process to show that $a'=\lambda a_2 + (1-\lambda)a''\,$ so $a'$ is on the segment between $a_2$ and $a''$ where $a''$ is a convex combination of $a_3, \cdots,a_k$, etc. In the end you'll get to a segment ending at $a_{k}\,$.

[ EDIT ]   Following up on a comment, as far as the geometric intuition goes, it may help to look at it from the end backwards:

  • you start at point $\,A_k=a_k\,$, which obviously belongs to the convex hull

  • then $\displaystyle\,A_{k-1}=\frac{c_{k-1} a_{k-1} + c_k a_k}{c_{k-1}+c_k}\,$ takes you to a point $A_{k-1}$ on segment $a_{k-1}a_k\,$, which again obviously belongs to the convex hull

  • next, $\displaystyle\,A_{k-2}=\frac{c_{k-2} a_{k-2} + c_{k-1} a_{k-1} + c_k a_k}{c_{k-2}+c_{k-1}+c_k}=\frac{c_{k-2} a_{k-2} +(c_{k-1}+c_k)A_{k-1}}{c_{k-2}+c_{k-1}+c_k}\,$ takes you to a point $A_{k-2}$ on segment $a_{k-2}A_{k-1}\,$, which is inside the triangle $a_{k-2}a_{k-1}{a_k}$ i.e. the convex hull of points $a_{k-2}, a_{k-1}, a_k\,$, therefore inside the convex hull of all points again

  • after $\,k\,$ steps you end up at $\,A_1=a\,$, and the entire path from $\,a_k\,$ to $\,a\,$ consists of line segments contained in the convex hull

dxiv
  • 76,497
  • Thanks. I am familiar with this sort of inductive argument. I suppose I am in the odd situation where I understand the proofs but still feel my geometric intuitiion is insufficient. Are you aware of the paper/textbook that first defined the notation of a convex combination (I imagine this might be quite old)? – 1729 Dec 28 '17 at 22:18
  • @TomHolt I am not aware of when "convex combination" was first defined or used, though pretty sure it must go far back. About the intuition, I added another way to look at it at the end of the answer. – dxiv Dec 28 '17 at 23:14