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$.

Details which I already know.

  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$.


2 Answers 2


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.

  • $\begingroup$ Yes. I realized this solution, but too late ;). $\endgroup$ Apr 16, 2012 at 0:38

My solution is incorrect. See other answer...

  • $\begingroup$ 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. $\endgroup$ Apr 9, 2012 at 4:09
  • $\begingroup$ I assumed it was not a homeowork problem... $\endgroup$ Apr 9, 2012 at 14:43
  • $\begingroup$ @Sariel: I found an easy proof. Should I post or do you want to think some more? $\endgroup$ Apr 13, 2012 at 14:20
  • 1
    $\begingroup$ Post away as a different answer, and then I would delete mine... $\endgroup$ Apr 14, 2012 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.