9
$\begingroup$

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

Improve this question
$\endgroup$
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes. I realized this solution, but too late ;). $\endgroup$
    – Sariel Har-Peled
    Apr 16 '12 at 0:38
8
$\begingroup$

My solution is incorrect. See other answer...

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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