# VC-dimension of spheres in 3 dimension

I am searching for the VC-dimension of the following set system.

Universe $U=\{p_1,p_2,\ldots,p_m\}$ such that $U\subseteq \mathbb{R}^3$. In the set system $\mathcal{R}$ each set $S\in \mathcal{R}$ corresponds to a sphere in $\mathbb{R}^3$ such that the set $S$ contains an element in $U$ if and only if the corresponding sphere contains it in $\mathbb{R}^3$.

1. The VC-dimension is atleast 4. This is because if $p_1,p_2,p_3,p_4$ are 4 corners of a tetrahedron then it can be shattered by $\mathcal{R}$

2. The VC-dimension is atmost 5. This is because the set system can be embedded in $\mathcal{R}^4$ with spheres in $\mathcal{R}^3$ corresponding to hyperplanes in $\mathcal{R}^4$. It is known that hyperplanes in $\mathcal{R}^d$ have VC-dimension $d+1$.

Here is an easy argument:

Assume there is a set $U$ of 5 points that can be shattered by balls. So for any set $S \subseteq U$, there exists a ball $B$ s.t. $B \cap U = S$ and a ball $B'$ s.t. $B' \cap U = U \setminus S$. Therefore, $B \cap B'$ contains no points of $U$. If $B \cap B' = \emptyset$, $B$ and $B'$ can be separated by a plane. Otherwise, the intersection of the surfaces of $B$ and $B'$ is a circle. The plane in which the circle lies separates $S$ from $U \setminus S$. Therefore, $U$ can be shattered by halfspaces, a contradiction.

The same argument in higher dimension shows that the VC-dimension of balls is equal to the VC-dimension of halfspaces.

• Yes. I realized this solution, but too late ;). – Sariel Har-Peled Apr 16 '12 at 0:38

My solution is incorrect. See other answer...

• Nopes, I am including this as an example in a talk. Instead of mentioning it as <=5 I thought it might be better to note the exact number. Thanks anyways. – Ashwinkumar B V Apr 9 '12 at 4:09
• I assumed it was not a homeowork problem... – Sariel Har-Peled Apr 9 '12 at 14:43
• @Sariel: I found an easy proof. Should I post or do you want to think some more? – Sasho Nikolov Apr 13 '12 at 14:20
• Post away as a different answer, and then I would delete mine... – Sariel Har-Peled Apr 14 '12 at 2:14