New answers tagged

3 votes

VC dimension of the class of all polygons with k vertices

Assuming that the $k$-gon is simple (i.e., does not intersect itself and has no holes) and $k>3$, the two-ears theorem, https://en.wikipedia.org/wiki/Two_ears_theorem implies that it can be ...
user avatar
  • 10k
2 votes
Accepted

Upper bound for VCdim of $H$ in terms of subgraph$(F)$, where $H := \{S(f) | f \in F\}$, with $S(f) := \{(x,y) \in X \times \{\pm 1\} | yf(x) \le 1\}$

Let us suppose that $H$ shatters some $k$ points $(x_i,y_i)$, $i\in[k]$. That means that for all $b\in\{0,1\}^k$, there is an $f=f_b\in F$ such that $y_if(x_i)\le\gamma$ if $b_i=1$ and $y_if(x_i)>\...
user avatar
  • 10k
1 vote
Accepted

VC-dimension of the infinite intersection of two spheres

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-...
user avatar
  • 10k

Top 50 recent answers are included