
What is the VCdimension of circles in the
plane ? I.e.,
examples are points in
and
c_{p,r}=1 if
x is within distance
r of
p. Or, in words, a legal target
function is specified by a circle, and labels any example positive
iff it lies inside that circle.
VCdim = 3. It is easy to see the VCdimension is at least 3
since any 3 points that make up a nondegenerate triangle can be
shattered.It is a bit trickier to prove that the VCdimension is
less than 4. Given 4 points, the easy case is when one is inside
the convex hull of th others. In that case, because circles are
convex, it is not possible to label the inside point
 and the outside points
+. Otherwise, call the points
a,b,c,d in
clockwise order. the claim is that it is not possible for one
circle c_{1} to achieve
labeling +,,+, and for some other
c_{2} to achieve labeling
,+,,+,. If such
c_{1},
c_{2} existed, then their symmetric
difference would consist of 4 disjoint regions, which is impossible
for circles.
