2
$\begingroup$

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?

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

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Popescu Claudiu
    Apr 30, 2022 at 15:38
  • $\begingroup$ Interesting, worth thinking about! $\endgroup$
    – Aryeh
    Apr 30, 2022 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.