# Convex hull approximated from inside by only finite number of elements?

In approximating the convex hull "from inside", i.e.

$$\text{conv}S = \{ x \in \mathbb{R}^n \mid x= \sum_{i=1}^k \lambda_i x^i, x^i \in S, \lambda_i \geq 0, \sum_{i=1}^k \lambda_i= 1 \} \text{,}$$

in the case where $S$ is infinite - why can we restrict ourselves to finite many $x^i \in S$?

-
The convex hull may consist of an infinite number of points, even in $n=2$. Consider a circle. I suppose your question is about "approximating", which perhaps means that the volume of the "inside" convex spans converge to the volume of ${conv}\; S$. –  hardmath Jul 30 '12 at 12:01
@hardmath I am not sure what you want to say. You can cancel out "approximation" and "inside" if this leads to confusion. It is just to seperate two ways of defining $\text{conv}S$, the one mentioned in my question, and the one $\text{conv}S = \cap_{S \subset M, M convex} M$ (this could be thought of "approximation from 'outside'"). One can define the convex hull without prior to introducing "extremal points", so I don't see why it should be relevant (Of course, for compact convex non-empty subsets of $\mathbb{R}^n$ we can reprsent the elements by a finite ($n+1$) sum of the extremal points.. –  Suedklee Jul 30 '12 at 14:08

I assume you are really asking this: Let $S$ be an infinite subset of $\mathbb{R}^n$. Then why is the convex hull of $S$, denoted $\operatorname{conv}S$, defined as you show it, using only finite convex combinations of elements of $S$?

The answer is that the set defined this way really is convex (a convex combination of two finite convex combination is another finite convex combination), and this is the smallest convex set containing $S$ (since any convex set containing $S$ must contain any finite convex combination of members of $S$).

I guess the main point is that the definition of convexity nowhere speaks of inifinite convex combinations.

As pointed out in the comments, Carathéodory's theorem is worth mentioning: It states that you never need to take a convex combination of more than $n+1$ of the points if you work in $\mathbb{R}^n$.

There is an analogy with linear combinations: The linear span of an infinite set of vectors consists of finite linear combinations of the given vectors.

-
Convex hull means the extremal points that generate a convex set, not the convex set (closure). But I think you've interpreted the question nicely, why does the convex closure's definition involve only finite sums. Carathéodory's theorem is probably worth mentioning in this connection, that for specific $x$ in $conv\;S$, at most $n+1$ of the generating points in $S$ are needed. –  hardmath Jul 30 '12 at 12:35
@hardmath: Thanks for reminding me of Carathéodory. I added that to the answer. I think you're wrong about convex hull, though. See the wikipedia link that I added to the answer. –  Harald Hanche-Olsen Jul 30 '12 at 12:54
Thanks for your answer! I actually came up with this question in the context of reading a proof of Carathéodory's theorem. I think my misunderstanding was that I thought the statement was that the same finitely many points $x_i, \dotsc, x_N \in S$ are enough to represent every $x \in \text{conv} S$ (in others words, for each set $S$, there are $x_1, \dotsc, x_N$ with $\text{conv} S = \text{conv} \{ x_1, \dotsc, x_N \}$). Which is not said in Carathéodory, and as I suppose wrong in general. –  Suedklee Jul 30 '12 at 13:21
I'm being more than a little pedantic, but "hull" conveys a sense of an outer covering (seed, boat). The Wikipedia article does define convex hull to be the convex closure, but then goes on to use it as well to mean the extremal points; see section Computation of convex hulls which talks about a (finite) "number of points on the convex hull". In any case two separate terms are needed to distinguish the set of extremal points and the set of convex combinations of suitable set $S$. –  hardmath Jul 30 '12 at 13:47
@hardmath: I don't think that section of the Wikipedia is particularly well written. But when they talk about “computing” the convex hull, they make clear that this means finding an “efficient representation” of the convex shape – which in finite dimensional space is best achieved by finding the extremal points. By the way, there already is a well established terminology for the set of extreme (or extremal) points: The extreme boundary. –  Harald Hanche-Olsen Jul 30 '12 at 14:05