1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – copper.hat Dec 28 '17 at 0:23
  • $\begingroup$ 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). $\endgroup$ – copper.hat Dec 28 '17 at 0:25
  • $\begingroup$ 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. $\endgroup$ – copper.hat Dec 28 '17 at 0:28
  • $\begingroup$ 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. $\endgroup$ – Nominal Animal Dec 28 '17 at 5:32
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – 1730 Dec 28 '17 at 22:18
  • $\begingroup$ @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. $\endgroup$ – dxiv Dec 28 '17 at 23:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.