# Classes of circle rims

The input space is a unit circle, $$\mathcal{X} = \mathbb{S}^1 \subset \mathbb{R}^2$$. There is class $$\mathcal{F}$$ of arcs on $$\mathbb{S}^1$$, where a point is labeled 1 if it is on the arc, and 0 otherwise. We want to find the VC dimension of $$\mathcal{F}$$

I think the answer is 2. Any two points can be shattered $$(++, -+, +-, --)$$. But if we have three points $$\{(x_1,y_1),\dots,(x_3,y_3)\}$$ that all have the label 1, with radius $$r_1 = r_2 = 1$$, and $$r_3 = 0$$, it is impossible to shatter them. Is my intuition correct?

• Have you tried proving your intuition? Apr 29, 2020 at 18:09
• It seems you can actually shatter every set of 3 points, but probably no set of 4 points. Apr 29, 2020 at 18:10
• Also, your point $(x_3,y_3)$ isn't an element of $\mathcal X$. Apr 29, 2020 at 18:11
• Make sure you understand the definition of VC dimension. Apr 29, 2020 at 18:11
• Yuval, you've been super helpful, if theres any comments or upgrade I can do to help your account, feel free to let me know. Back to the question, Ill have to show that some $d$ can be shattered, but not $d+1$. For $d=2$ its clear from above. If $d=3$, can be shattered, then it must be the case that all three points can be classified correctly -- does it mean all three points dont have to be in a single line? Then I can see why three points can be shattered but not four. If this is the case, why isn't it necessary to place the points on the line? Thanks
– user120261
Apr 29, 2020 at 18:18

In fact, the VC dimension is 3.

To show this, we need to show that there is a set of 3 points which is shattered, and that no set of 4 points is shattered.

All sets of 3 points behave the same, but for definiteness let us choose three points $$x,y,z$$ which form the corners of an equilateral triangle. By symmetry, there are only 4 cases to consider:

• $$\emptyset$$: choose some arc which avoids all points.
• $$\{x,y,z\}$$: choose the complement arc.
• $$\{x\}$$: choose a small arc around $$x$$.
• $$\{y,z\}$$: choose the complement arc.

This shows that the VC dimension is at least 3.

To show that the VC dimension is at most 3, let us consider some arbitrary set of points $$x,y,z,w$$, presented in clockwise order starting at an arbitrary point. An arc that contains both $$x$$ and $$z$$ must contain either $$y$$ or $$w$$, and in particular there is no arc that contains exactly $$\{x,z\}$$.