What is the VC-dimension of triangles in
the plane ? I.e., a legal target function is
specified by a triangle, and labels any example positive iff it
lies inside that triangle.
VC-dim = 7. Given 7 points on a
circle, they can be labeled in any desired way because in any
labeling, the negative examples form at most 3 contiguous blocks.
Therefore one edge of the triangle can be used to cut off each
block. However, no set of 8 points can be shattered. If one of the
points is inside the convex hull of the rest, then it is not
possible to label that point negative and the rest positive.
Otherwise, it is not possible to label them in alternating