# VC Dimension of Origin-Centered Circle

Is the VC dimension of an origin-centered circle 1 or 2?

It seems to me that the VC dimension of an origin centered circle should be 1, because for two points with distances from the origin r1 <= r2, r2 will never be able to be labeled 1 without r1 also being labeled 1, so the r1 = 0, r2 = 1 labeling could never be possible.

However, this and this both say that an origin-centered circle has VC dimension of 2.

What you are missing is a definition of origin-centered circles. The definition of the slides (your second link) is wrong, for the reasons you mention. The definition in the lecture notes (your first link) makes it clear that you can choose whether it is the inside or the outside of the circle which gets the value +1, and this shows that any two points whose distance from the origin is not the same can be shattered, and so the VC dimension is at least 2.

• Precisely! an origin-centered circle is F(r) = x^2 + y^2 - r^2. VC dimension depends on the Hypothesis Class. If its F(r) < 0 or F(r) > 0, then VC dimension is 1 like you said. If its a.F(r) < 0 (a is the sign), then its 2. In general VC dimension is the no of true parameters of the hypothesis class. (r, a in the case where VC dim is 2) Feb 17 '20 at 18:18

Assume that the points on the circle are considered inside. With that if you have 2 points at an equal distance from the origin, you cannot label one + and the other -. Either both are in or both are out. On the contrary for 3 points with varying distance from the origin, you can label them +, -, +. This arrangement cannot be shattered. Hence the VC dimension is 2.

Consider the distance as an attribute and +/- as a label. For the same set of attributes, you cannot have a different label.

Why are you excluding the case where the distance is the same? Take any two points with equal distanced from the origin and they cannot be shatters -> VC is 1

• The VC dimension is the maximum number of points that can be arranged such that they are shattered. It is irrelevant that some arrangements of two points cannot be shattered, all that matters is that there is an arrangement that can be shattered. Feb 5 '19 at 6:51
• With that you can also say that the VC dimension is 3, or 4, or 5.. no? Just put all the points that are closer to the origin than the radius as positives(+) and the others as negatives. Feb 5 '19 at 18:18
• No, a circle at the origin cannot shatter 3 or more points. In that case, there is a point that is closer (or equal distance) to the origin than some point and further from the origin than some other point, i.e. there is a point in the "middle". Each origin centered circle that contains the middle point contains a closer point and each circle that does not contain the middle point does not contain a further point. Hence, the middle point cannot be in a different class from both the closer and the further pint. Feb 5 '19 at 21:37
• I'm still not clear on why you are excluding the case where the 2/3/4 points are at an equal distance from the origin. can you explain that? Feb 6 '19 at 20:44
• I am not excluding that case. The argument still works if the points are at equal distance. In fact, an even simpler argument works in that case. I've said quite a bit here, I suggest you have another look at the definition of shattering and VC-dimension and try to work it out on your own. If that doesn't help you, I suggest you ask a question. Be sure to explain in the question what you tried and where you got stuck. Feb 6 '19 at 21:46