2
$\begingroup$

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?

$\endgroup$
0

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.