<p>My solution is incorrect. See other answer...</p>

CC BY-SA 3.0
2012-04-09T04:09:56.093Z
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
CC BY-SA 3.0
2012-04-09T14:43:45.933Z
I assumed it was not a homeowork problem...
Sariel Har-Peled
CC BY-SA 3.0
2012-04-13T14:20:18.393Z
@Sariel: I found an easy proof. Should I post or do you want to think some more?
Sasho Nikolov
CC BY-SA 3.0
2012-04-14T02:14:46.647Z
Post away as a different answer, and then I would delete mine...
Sariel Har-Peled
CC BY-SA 3.0
2012-04-09T04:01:09.620Z
2012-04-15T15:08:13.350Z
2012-04-15T15:08:13.350Z
Sariel Har-Peled
<p>Here is an easy argument:</p>

<p>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&#39;$ s.t. $B&#39; \cap U = U \setminus S$. Therefore, $B \cap B&#39;$ contains no points of $U$. If $B \cap B&#39; = \emptyset$, $B$ and $B&#39;$ can be separated by a plane. Otherwise, the intersection of the surfaces of $B$ and $B&#39;$ 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.</p>

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

CC BY-SA 3.0
2012-04-16T00:38:04.267Z
Yes. I realized this solution, but too late ;).
Sariel Har-Peled
CC BY-SA 3.0
2012-04-14T16:24:03.853Z
2012-04-14T16:24:03.853Z
Sasho Nikolov
<p>I am searching for the VC-dimension of the following set system.</p>

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

<p>Details which I already know.</p>

<ol>
<li><p>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}$</p></li>
<li><p>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$.</p></li>
</ol>

<cg.comp-geom><machine-learning><vc-dimension>
VC-dimension of spheres in 3 dimension
Ashwinkumar B V
# VC-dimension of spheres in 3 dimension

(Asked by: username_0 on 2012-04-08)

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

**Tags:** cg.comp-geom, machine-learning, vc-dimension


---

## 2 answers

### Answer by username_2 on 2012-04-14. Score: 11 | Accepted answer

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.

> **Comments:**
> **username_1**: Yes. I realized this solution, but too late ;).  

---

### Answer by username_1 on 2012-04-09. Score: 8

My solution is incorrect. See other answer...

> **Comments:**
> **username_0**: 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.  
> **username_1**: I assumed it was not a homeowork problem...  
> **username_2**: @Sariel: I found an easy proof. Should I post or do you want to think some more?  
> **username_1**: Post away as a different answer, and then I would delete mine...  

---

