<p>Once the OP has clarified that the question is about the VC-dimension of the 2-fold intersection of spheres in <span class="math-container">$\mathbb{R}^d$</span> (in fact, <span class="math-container">$d=2$</span> was specified), a simple upper bound can be stated. The VC-dim of spheres in <span class="math-container">$\mathbb{R}^d$</span> is the same as that of half-spaces (via an easy scaling argument) --- namely, <span class="math-container">$d+1$</span>.
Lemma 3.2.3 of Blumer et al. (1989) bounds the VC-dim of the <span class="math-container">$k$</span>-fold union/intersection of a class of VC-dim <span class="math-container">$d$</span> by
<span class="math-container">$$
2kd\log(3k).
$$</span>
Thus, <span class="math-container">$2\cdot2\cdot2\log(6)\approx 14$</span> is an upper-bound on the VC-dimension in the OP.</p>
<p>A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. J. Assoc. Comput. Mach., 36(4):929–965, 1989. ISSN 0004-5411.</p>

CC BY-SA 4.0
2022-04-21T09:29:43.713Z
Thank you very much!
shai
CC BY-SA 4.0
2022-04-20T21:47:16.467Z
2022-04-21T10:15:52.267Z
2022-04-21T10:15:52.267Z
Aryeh
<p>I'm searching for an upper-bound for the VC-dimension of the infinite intersection of two spheres.
Thanks</p>

CC BY-SA 4.0
2022-04-20T14:21:38.610Z
How many spheres are interesting—two or infinity? And in what space? Finite-dimensional Euclidean or more exotic?
Aryeh
CC BY-SA 4.0
2022-04-20T20:57:49.040Z
To be more precise, VC-dimension of the infinite phases of the moon. Each phase is the intersection of two spheres. In 2D
shai
<machine-learning><vc-dimension>
VC-dimension of the infinite intersection of two spheres
shai
# VC-dimension of the infinite intersection of two spheres

(Asked by: username_0 on 2022-04-20)

I'm searching for an upper-bound for the VC-dimension of the infinite intersection of two spheres.
Thanks

**Tags:** machine-learning, vc-dimension

> **Comments:**
> **username_1**: How many spheres are interesting—two or infinity? And in what space? Finite-dimensional Euclidean or more exotic?  
> **username_0**: To be more precise, VC-dimension of the infinite phases of the moon. Each phase is the intersection of two spheres. In 2D  

---

## 1 answers

### Answer by username_1 on 2022-04-20. Score: 1 | Accepted answer

Once the OP has clarified that the question is about the VC-dimension of the 2-fold intersection of spheres in $\mathbb{R}^d$ (in fact, $d=2$ was specified), a simple upper bound can be stated. The VC-dim of spheres in $\mathbb{R}^d$ is the same as that of half-spaces (via an easy scaling argument) --- namely, $d+1$.
Lemma 3.2.3 of Blumer et al. (1989) bounds the VC-dim of the $k$-fold union/intersection of a class of VC-dim $d$ by
$$
2kd\log(3k).
$$
Thus, $2\cdot2\cdot2\log(6)\approx 14$ is an upper-bound on the VC-dimension in the OP.

A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. J. Assoc. Comput. Mach., 36(4):929–965, 1989. ISSN 0004-5411.

> **Comments:**
> **username_0**: Thank you very much!  

---

