# VC dimension of only the rim of a unit disk

Suppose we have an origin centered circle, ie $$x^2 + y^2 =1$$, so it's in $$\mathbb{R}^2$$ (2D). It will be classified as 1 if it lies only on this arc, and will be labeled 0 otherwise. What is the VC dimension?

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?

Or can I construct the sample points to my liking (to get the maximum VC dim) so that only the positive labels will be on the rim (have some combination of $$x_i^2 + y_i^2 = 1$$), and have 0 labels to not lie on the rim, therefore have infinite VC dimension?

• The VC dimension is a feature of a class of functions. If the VC dimension is $d$, then the class of functions has to contain at least $2^d$ different functions. You are describing a class of functions consisting of a single function. Hence its VC dimension is zero. – Yuval Filmus Apr 29 '20 at 7:31
• Sorry I don't quite get why it is zero. If we have $d = 2$, then we can always place the two samples $S = {(x_1,y_1),(x_2,y_2)}$ either on the arc or not on the arc without misclassifying any other sample... Doesn't this show that it contains at least $2^2$ functions, thus VC is at least 2? Could you also elaborate more about "You are describing a class of functions consisting of a single function"? – user120261 Apr 29 '20 at 14:33
• In your post you are describing a single function $\mathbb{R}^2 \to \{0,1\}$, which is $1$ on input $(x,y)$ iff $x^2 + y^2 = 1$. As far as I know, this is the only function in your class. If not, you'll have to specify your class of functions explicitly. I can't read your mind! – Yuval Filmus Apr 29 '20 at 14:35
• No, you are correct, this is the only function from $\mathbb{R}^2$ to $\{0,1\}$. So proceeding from here, if I have 2 samples, wouldn't it be possible to place the $1$ label on the arc, the $0$ label outside of the arc, shattering $d=2$? On the contrary, If I have three labels all on the x-axis, then it is impossible to label all 1's (only two can be labeled 1 at (-1,0) and (1,0))? Please advise. Thanks for the time! – user120261 Apr 29 '20 at 15:20
• I suspect that you are understanding the question wrong. (You also seem to be misunderstanding the definition of VC dimension.) – Yuval Filmus Apr 29 '20 at 15:33

Let $$\mathcal F$$ be a class of functions from $$\mathcal X$$ to $$\{0,1\}$$. If $$\mathcal F$$ has VC dimension $$d$$ then $$|\mathcal F| \geq 2^d$$.
Indeed, if $$\mathcal F$$ has VC dimension $$d$$ then $$\mathcal F$$ shatters some set $$S \subseteq \mathcal X$$ of size $$d$$. This means that for any function $$\phi\colon S \to \{0,1\}$$ we can find a function $$f_\phi \in \mathcal{F}$$ that agrees with $$\phi$$ on $$S$$. Note that if $$\phi \neq \psi$$ then $$f_\phi \neq f_\psi$$. Since there are $$2^d$$ different functions from $$S$$ to $$\{0,1\}$$, we conclude that $$\mathcal F$$ must contain at least $$2^d$$ functions. $$\square$$