= VC dimension of Euclidean balls
{c}
{title2=$\operatorname{VC}(\mathcal B_d)=d+1\quad(d\geq1)$}
The positive-radius closed <Euclidean balls> in $\mathbb R^d$ have <VC dimension> $d+1$ for $d\geq1$. Vertices of a <regular simplex> are shattered: interpolate any desired signs by an <affine function> $a\cdot x+b$, then perturb a sphere through the vertices to the score $1+\eta b+\eta a\cdot x-\|x\|^2$. For the upper bound, take an <affine dependence> $\lambda$ among $d+2$ points and orient it so that $Q=\sum_i\lambda_i\|x_i\|^2\geq0$. Labelling the positive coefficients inside and the negative coefficients outside would force $\sum_i\lambda_i(r^2-\|x_i-c\|^2)>0$, while the <affine dependence> makes this sum equal $-Q\leq0$. The weaker $d+2$ upper bound from unrestricted lifted <affine linear classifiers> loses their fixed quadratic coefficient.
Back to article page
