Question

How can we show that the VC dimension of a circle of dimension d is (d+1)

Answer 1

For any three noncollinear points, we can easily draw a circle that includes all three of them, any two
of them, any one of them, or none of them, so any three noncollinear points are shattered by the class
of circles.
However, for any set of four points, they are not shattered. We show this by constructing a
counterexample in several cases:
1. If the four points are collinear, the labeling +-+- (going along the line) is impossible, among
numerous others.
2. If the convex hull of the four points is a triangle, then the labeling with +(the three points of the
triangle) and -(the interior point) is not possible.
3. If the convex hull of the four points is a quadrilateral, then let (a1; a2) be the points separated
by the long diagonal and (b1; b2) be the points separated by the short diagonal. At least one of the
labelings +(a1; a2);-(b1; b2), +(b1; b2);-(a1; a2) must be impossible: if they were both possible, then
there would be some satisfying circle c1 for the rst labeling and some other circle c2 satisfying the
second labeling, and the symmetric dierence of these circles ((c1 \ c2) union (c2 \ c1)) would consist of
four disjoint regions, which is impossible for circles.
Since some set of 3 points is shattered by the class of circles, and no set of 4 points is, the
VC dimension of the class of circles is 3.

For Spheres in N dimension it is same as HalfSpaces.

the convex hull of a set of points S is the set of all convex combinations of points S;
It is the same as that of half spaces. First, we prove that no set of
d + 2 points can be shattered by spheres. Suppose some set S with d + 2 points can be
shattered. Then for any partition A1;A2 of S, there are spheres B1 and B2 such that
B1 and S = A1 and B2 and S = A2. Now B1 and B2 may intersect, but there is no point of S
in their intersection. It is easy to see that there is a hyperplane with all of A1 on one side
and all of A2 on the other and this implies that half spaces shatter S, a contradiction.
Therefore no d + 2 points can be shattered by hyperspheres.