= Solution
An <affine linear classifier> in $\mathbb R^k$ has <VC dimension> $k+1$. The upper bound follows from the <intersecting convex hull partition theorem>: for any $k+2$ points, label the two parts oppositely. The two <convex hulls> cannot be strictly separated by an <affine hyperplane>, since they intersect. A weak boundary convention gives the same contradiction: an affine score is nonnegative on the positive <convex hull> and strictly negative on the negative <convex hull>. The lower bound comes from the $k+1$ <affinely independent> vertices of a <simplex>, because an affine score can interpolate arbitrary signs there.
Consequently, parts (i) and (ii) immediately give
$$
\boxed{d+1\leq\operatorname{VC}(\mathcal B_d)\leq d+2.}
$$
The one-sided orientation of the lifted separators permits the sharper, exact conclusion
$$
\boxed{\operatorname{VC}(\mathcal B_d)=d+1\qquad(d\geq1).}
$$
To prove the remaining upper bound, take any $d+2$ distinct points and a nonzero <affine dependence> $\lambda_i$ as in part (c). Write $Q=\sum_i\lambda_i\|x_i\|^2$. Reverse every coefficient if necessary so that $Q\geq0$. Prescribe positive labels when $\lambda_i>0$ and negative labels when $\lambda_i<0$; zero coefficients may be labelled arbitrarily. If a <Euclidean ball> realized these labels, its score $g(x)=r^2-\|x-c\|^2$ would satisfy
$$
\sum_i\lambda_i g(x_i)>0.
$$
Indeed, every positive-coefficient term is nonnegative and every negative-coefficient term is strictly positive, with at least one of the latter. On the other hand, expanding the score and using the two <affine dependence> identities gives
$$
\sum_i\lambda_i g(x_i)
=(r^2-\|c\|^2)\sum_i\lambda_i+2c\cdot\sum_i\lambda_i x_i-\sum_i\lambda_i\|x_i\|^2
=-Q\leq0,
$$
a contradiction. No $d+2$ points are shattered, completing the exact determination of the <VC dimension of Euclidean balls>. In the exceptional zero-dimensional <Euclidean space>, every positive-radius <Euclidean ball> is the whole singleton space, so the <VC dimension> is zero.
Back to article page
