VC-dimension for spheres

Answer 1

If we are considering spheres of dimension d then the following argument shows that the VC dimension of these spheres cannot be more than O(d2). Notice that the equation of a sphere is a quadratic equation and has (d+1)2 coefficients. Lets work in R2 for clarity - any sphere looks like s(x,y) = ax2+bxy+cy2+dx+ey+f = 0 and a point (x,y) is in the sphere if s(x,y) < 0 and outside if s(x,y) > 0.

Now simply interpret this situation in a 5 dimensional space with a new set of coordinates X,Y,Z,V,W. Simply make a change of coordinates X = x2, Y = xy, Z = y2, V = x, W = y. In this new space the old quadratic equation simply looks like a hyperplane ! Since the VD dimension of d-dimensional hyperplanes is d+1, we realize that the spheres in d-dimensions are no more powerful than hyperplanes in O(d2) dimensions and hence have a VC dimension of O(d2).

I do not know if this argument can be tightened.