At least 3 points on the convex hull

alternative-proofcombinatorial-geometryconvex-hulls

It's almost obvious that for any point set that contains at least 3 points on the Euclidean plane the boundary of its convex hull must contain at least 3 of the points. I worke out a proof (not sure whether it's right), but it relies so much on the concept of "rotation", or "angles" (if someone wants to see the proof please tell me, I'll add that). I wonder if there's a more general proof, or even only using the axioms, as there the concept of "angles" in higher dimensions is quite different.

To simplify: for any point set that contains at least 3 points on the Euclidean plane the boundary of its convex hull must contain at least 3 of the points; is it possible to prove this without using the concept of "angles"?


EDIT. Due to the answer of Theo Bendit a counterexample do exists. Therefore I'm restricting the point set to discrete point set.

Best Answer

Not in general, I'm afraid. Suppose you have the set $$\{(x, 0) : |x| < 1\} \cup \{(0, y) : |y| < 1\},$$ i.e. the $x$ and $y$-axes intersected with the open unit disc centred at $0$ (which forms a $+$ sign without the tips), and compute its convex hull. Then you will get an open diamond (the unit ball of the $1$-norm): $$\{(x, y) : |x| + |y| < 1\}.$$ This set is open, and contains none of its boundary points, let alone any of the points used to generate the set.

Here's another example: consider the set convex hull of the set: $$\{(x,1/x) : x > 0\} \cup \{(-x, 1/x) : x > 0\},$$ i.e. the graph of the function $|x|^{-1}$. Then the convex hull will be the entire open upper half-plane, i.e. everything above (but not including) the $x$-axis. Once again, no boundary means no points from the original set in the boundary.

There are ways to rectify this. The big, over-the-top, sledghammer-to-kill-a-fly tool here is the Krein-Milman theorem, and Milman's converse to the Krein-Milman theorem. The Krein-Milman theorem states:

Suppose $X$ is a Hausdorff locally convex topological vector space (or $\Bbb{R}^n$ will do fine), and $K$ is a compact, convex subset of $X$. Then $X$ is the closed convex hull of its extreme points.

Milman's converse helps bring it home:

Suppose $X$ is a Hausdorff locally convex topological vector space (or $\Bbb{R}^n$), $T \subseteq X$ is such that the closed, convex hull of $T$ is compact. Then, every extreme point belongs to the closure of $T$.

So, if we can guarantee that our closed, convex hull is compact, and our generating set is closed (which is the case if it's compact, at least in normed linear spaces), then we can reduce our generating set to just the extreme points. If there are two extreme points or fewer, then the set would have to be contained in a line segment, and embedded in a space of $2$ (or more) dimensions, every point would be on the boundary. Otherwise, there are at least $3$ extreme points, all of which must be on the boundary of the closed convex hull.

Note: the assumption that the closed convex hull cannot be dispensed with. In my second example, the set given is closed, but its closed convex hull contains no extreme points, and (once again) the boundary contains none of the original points. This does fix the first example though: if you take the closure (replace the $<$ with $\le$), then the closed convex hull will be compact, and the four extreme points $(\pm 1, 0), (0, \pm 1)$ all lie within the original set.

Related Question