# VC dimension of the class of all polygons with k vertices

VC dimension of the class of convex polygons with $$k$$ vertices is known to be $$2k + 1$$.

For the general case I was able to derive a bound of the type $$O(k^2log(k))$$ (probably can be easily improved to O(klog(k)), this is not the issue). However, I found some hits (e.g. https://cs.nyu.edu/~mohri/ml/ml08/sol2.pdf) that VC dimension for this case is in fact also $$2k + 1$$. Any idea if this is correct?

• Which of Mohri’s arguments gives you indication that it’s 2k+1? I don’t see it. Apr 24, 2022 at 8:42
• Indeed, there's no argument in dat document, just a statement. Apr 30, 2022 at 15:44

Assuming that the $$k$$-gon is simple (i.e., does not intersect itself and has no holes) and $$k>3$$, the two-ears theorem, https://en.wikipedia.org/wiki/Two_ears_theorem implies that it can be triangulated -- i.e., expressed as a union of $$k$$ or fewer triangles. Now triangles in the plane have VC-dim 7, and, by Lemma 3.2.3 of Blumer et al. (1989), $$k$$-fold unions of triangles have VC-dim at most $$14k\log(3k)=O(k\log k).$$ I still don't see how you can get $$2k+1$$.