VC dimension of half planes Let $\mathcal H$ be the set of all half spaces in the two-dimensional plane ($\mathbf{R}^2$).
Two questions.
1) How can we formally show that the VC dimension of our half spaces is 3? That is, how can we formally show that it is impossible to shatter four points (i.e. perfectly classify some set of four points using half spaces).
2) If the separating line passes through the origin, what is the VC dimension? I want to think that it is 2 in this case, but what if one of the points is on the origin?
Many thanks
 A: 1): We need to prove that there is a set $C\subset \mathbb R^2$ such that $|C|=3$, and $C$ is shattered by $\mathcal H$. I assume you have already done so, but if not the easiest is most probably taking $C=\{(0,0),(1,0),(0,1)\}$, from which you can explicitly calculate the relevant half-planes.
Now let us consider an arbitrary set, $C=\{c_1,c_2,c_3,c_4\}\subset \mathbb R^2$. Radon's Theorem guarantees that we can partition $C$ into two disjoint sets, $P_1$ and $P_2$ such that their convex hulls intersect. Let us say w.l.o.g that $P_1=\{c_1,c_2\}$ and $P_2=\{c_3,c_4\}$. Now the convex hull of a two point set is just the line segment joining those two points. Thus we have $\overline{c_1c_2}\cap \overline{c_3c_4}\neq\emptyset$. Now let us assume that there exists some line such that $c_1$ and $c_2$ lie on one side, and $c_3$ and $c_4$ on the other. Then $\overline{c_1c_2}$ must also lie entirely in that half-plane containing $c_1$ and   $c_2$, and $\overline{c_3c_4}$ must lie entirely in the opposite half-plane. This contradicts the fact that these two line segments intersect. Thus $C$ cannot be shattered by $\mathcal H$.
2): Once again finding a set $C$ with $|C|=2$ shattered by $\mathcal H_0$ is easy. To prove that the VC dimension is $2$ we can just consider the triangle joining the 3 points (or consider the non-homogenous case in $\mathbb R$ as detailed in the next paragraph). We can show that it is impossible to separate each point from the other 2. Just consider what happens with the separating hyperplane passing on either side of the vertex nearest to the origin. If the one point is the origin it doesn't matter, because you'll never be able to have a half-space that contains all 3 points as well as one that contains none of the points. If you are considering open half-spaces, then none of the half-spaces will contain the origin.
It is interesting to note that the VCdimension of half-spaces on $\mathbb R^{n-1}$ is always the same as the VCdimension for half-spaces centred at the origin on $\mathbb R^n$. We can prove that the VCdimension of non-homogenous half-spaces on $\mathbb R^n$ is n+1 using Radon's Theorem, and we can pass between the the homogenous case in $\mathbb R^{n+1}$ to the non-homogenous case in $\mathbb R^n$ by using the argument outlined at the bottom of page 4 in these notes.
