VCdim of planes in 3D

Question

I new in the site. I'm self study Discrete Geometry, in my study I go thourh one problem that I not sure about it's solution.

Q: Consider the range space $\left(\mathbb{R}^{3}, \mathcal{H}_{3}\right)$, where $\mathcal{H}_{3}$ denotes all the planes (i.e., hyperplanes) in $\mathbb{R}^{3} .{ }^{1}$ Show that $\operatorname{VCdim}\left(\mathbb{R}^{3}, \mathcal{H}_{3}\right)=3$.

${ }^{1}$ Namely, each plane is determined by a certain linear equality $a x+b y+c z=1$ or $a x+b y+c z=0$, with $a, b, c \in \mathbb{R}$ and not all 0 , and is comprised of all the points $(x, y, z) \in \mathbb{R}^{3}$ that satisfy this equality.

I tried to solve the problem, but i think that my solution is not correct.

A:

To show that $\operatorname{VCdim}\left(\mathbb{R}^{3}, \mathcal{H}_{3}\right)=3$, we need to show that:

There exists a set of 3 points that can be shattered by $\mathcal{H}_3$, i.e., for any labeling of these 3 points, there exists a hyperplane in $\mathcal{H}_3$ that separates the points according to their labels.

Any set of 4 points cannot be shattered by $\mathcal{H}_3$, i.e., there exists a labeling of these 4 points such that no hyperplane in $\mathcal{H}_3$ can separate the points according to their labels.

To prove the first statement, we can consider the following set of 3 points: $(1,0,0)$, $(0,1,0)$, and $(0,0,1)$. We can label these points as ${-1,1}$ in all possible ways. For any labeling, we can find a hyperplane in $\mathcal{H}_3$ that separates the points according to their labels. For example, if we label $(1,0,0)$ and $(0,1,0)$ as 1 and $(0,0,1)$ as $-1$, we can choose the hyperplane $z=0$ which separates the positive and negative points.

To prove the second statement, we can consider any set of 4 points that lie on a common plane, say $ax+by+cz=d$, where $(a,b,c)\neq (0,0,0)$. Without loss of generality, we can assume that the 4 points are $(1,0,\frac{d-a}{c})$, $(0,1,\frac{d-b}{c})$, $(1,1,\frac{2d-a-b}{c})$, and $(0,0,\frac{d}{c})$. We can label these points as ${-1,1}$ in all possible ways. However, we can show that no hyperplane in $\mathcal{H}_3$ can separate the points according to their labels.

Suppose there exists a hyperplane $ax+by+cz=e$ that separates the points according to their labels. Without loss of generality, we can assume that $(1,0,\frac{d-a}{c})$ and $(0,1,\frac{d-b}{c})$ are labeled as 1, and $(1,1,\frac{2d-a-b}{c})$ and $(0,0,\frac{d}{c})$ are labeled as $-1$. Since $(1,0,\frac{d-a}{c})$ and $(0,1,\frac{d-b}{c})$ are both labeled as 1, they must lie on the positive side of the hyperplane. Therefore, we have $a+b>0$ and $c>0$. Similarly, since $(1,1,\frac{2d-a-b}{c})$ and $(0,0,\frac{d}{c})$ are both labeled as $-1$, they must lie on the negative side of the hyperplane. Therefore, we have $a+b<0$ and $c<0$. However, these two conditions cannot be satisfied simultaneously, which means that there is no hyperplane in $\mathcal{H}_3$ that can separate the 4 points according to their labels.

Therefore, we have shown that $\operatorname{VCdim}\left(\mathbb{R}^{3}, \mathcal{H}_{3}\right)=3$.

In my opinion, it's not a proof, but I not sure what is missing and how to word it better as a proof.

Answer 1

The correct interpretation of "a family of sets $\scr F$ shattering set $X$" means that for the set $X\subseteq \mathbb R^3$, choosing any subset $S$ of the $X$, there is a set $F$ in the family of sets $\mathscr F := \mathcal H_3$ s.t. $X \cap F = S$ (in words we say "$F\in \scr F$ cuts out (precisely/exactly) the subset $S$ of $X$"). Your interpretation is taking $\scr F$ to be the set of all half-spaces in $\mathbb R^3$.

To show the VC-dimension is $<4$, we show that for any set of 4 points $X:=\{x_1,\ldots, x_4\}\subset \mathbb R^3$, there is some subset $S\subseteq X$ s.t. there is no way for a hyperplane (i.e. a set $F \in \scr F$) to cut out precisely that set $S$ from $X$. We have 2 cases:

• If the points are not coplanar, then indeed $X$ itself can not be cut out by any hyperplane (by definition of coplanar).
• If the points are coplanar, then either:
  • the points are colinear, in which case every hyperplane which passes through 2 of the points contains the unique line that passes through all 4 points; hence subsets of $X$ of cardinality/size 2 can't be precisely cut out by planes.
  • OR, the points are not colinear, in which case there are 3 noncolinear points with a unique plane passing through them, which by uniqueness must be the plane that passes through all 4 points. Thus there is a subset of cardinality/size 3 that can't be precisely cut out by planes.

---

If you want to tackle the $\mathscr F:=$ half-spaces problem, you can use https://en.wikipedia.org/wiki/Hyperplane_separation_theorem to show that any set of 4 points in $\mathbb R^3$ that are not coplanar can be shattered by $\scr F$ (hint: take convex hulls of certain subsets and their complements; the resulting 2 compact convex sets will be disjoint by the condition that the 4 points are not coplanar), which shows that in this case $\text{VCdim}(\mathbb R^3, \scr F) \geq 4$.