How can I show that the VC dimension of the set of all closed balls in $\mathbb{R}^n$ is at most $n+3$?

For this problem, I only try the case $n=2$ for 1. When $n=2$, consider 4 points $A,B,C,D$ and if one point is inside the triangle formed by the other three, then we cannot find a circle that only excludes this point. If $ABCD$ is convex assume WLOG that $\angle ABC + \angle ADC \geq 180$ then use some geometric argument to show that a circle cannot include $A,C$ and exclude $B,D$.

For the general case I’m thinking of finding $n+1$ points so that a ball should be quite ‘large‘ to include them, and that this ball can not exclude the other 2 points. However, in high-dimensional case I do not know how to use maths language to describe what is ‘large’.

Can anyone give some ideas to this question please?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.