# 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. Commented Apr 24, 2022 at 8:42
• Indeed, there's no argument in dat document, just a statement. Commented Apr 30, 2022 at 15:44

## 1 Answer

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$$.

A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. J. Assoc. Comput. Mach., 36(4):929–965, 1989. ISSN 0004-5411.

• Thank you, Aryeh! I used the same lemma, but with a "convex partition by segments" - cs.jhu.edu/~misha/Spring16/05.pdf . I still have an intuition (which can very well be wrong) that it might be 2k +1. My reasoning is like this: a) For any n points, even for general polygons, the best case (maximum number of label assignments ) is still achieved for points that are all vertexes of the convex hull. In that case, the fact that non-convex polygons can be used is not useful- the VC dimension is the same as in the case of convex polygons. However, I was not able to actually show this. Commented Apr 30, 2022 at 15:38
• Interesting, worth thinking about! Commented Apr 30, 2022 at 18:45