0

I read wikipedia's proof of Caratheodry's theorem for convex sets. I was wondering if there exists a more geometric proof.

I was thinking of something along the following line of reasoning.

The theorem:

Given a set $P$ of points in $R^d$. A point $x$ in the convex hull can be written as a convex combination of at most $d+1$ points in $P$.

There is a line from a point $p'\in P$ to $x$. This line must intersect the boundary of the polyhedron, say at $y$. (Which is bounded because it is the convex hull of a finite set of points.)

Then $x=\lambda p' + (1-\lambda)y$ where $0 \le \lambda \le 1$

This boundary is a face of the polyhedron which lives on a $d-1$ dimensional subspace. Therefore by induction, $y$ is a convex combination of d points in $p$ and therefore $x$ is a convex combination of $d + 1$ points.

The base case for the induction argument just is that for points in any 1 dimensional subspace, one can just take the two outer points to make a convex combination of any points in the convex set.

Jeff
  • 853
  • 1
    Why are you assuming that $P$ is finite in the proof.. There's nothing about that in the hypothesis? – saulspatz Jan 28 '18 at 01:42
  • Good question. :). In the book, I was reading, Introduction to Linear Optimization, by Bertsimas, they describe the theorem as: Let $A_1...A_n$ be a collection of vectors in $R^m$ with $P$ the convex hull of the vectors $A_i$. So, assumed it was dealing with convex hulls of finite sets of points. I now see that the theorem is a bit more general than that. – Jeff Jan 28 '18 at 02:23
  • However, I think my proof could be generalized to that case, but it would become more messy. – Jeff Jan 28 '18 at 02:28

0 Answers0