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

CC BY-SA 4.0
2022-04-30T15:38:10.817Z
Thank you, Aryeh! I used the same lemma, but with a "convex partition by segments" - https://www.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.
Popescu Claudiu
CC BY-SA 4.0
2022-04-30T18:45:00.077Z
Interesting, worth thinking about!
Aryeh
CC BY-SA 4.0
2022-04-29T14:17:10.360Z
2022-04-29T14:17:10.360Z
Aryeh
<p>VC dimension of the class of convex polygons with <span class="math-container">$ k $</span> vertices is known to be <span class="math-container">$ 2k + 1$</span>.</p>
<p>For the general case I was able to derive a bound of the type <span class="math-container">$ O(k^2log(k)) $</span> (probably can be easily improved to O(klog(k)), this is not the issue). However, I found some hits (e.g. <a href="https://cs.nyu.edu/%7Emohri/ml/ml08/sol2.pdf" rel="nofollow noreferrer">https://cs.nyu.edu/~mohri/ml/ml08/sol2.pdf</a>) that VC dimension for this case is in fact also <span class="math-container">$2k + 1$</span>. Any idea if this is correct?</p>

CC BY-SA 4.0
2022-04-24T08:42:57.447Z
Which of Mohri’s arguments gives you indication that it’s 2k+1? I don’t see it.
Aryeh
CC BY-SA 4.0
2022-04-30T15:44:06.603Z
Indeed, there's no argument in dat document, just a statement.
Popescu Claudiu
<machine-learning><computational-geometry><vc-dimension><pac-learning>
VC dimension of the class of all polygons with k vertices
Popescu Claudiu
# VC dimension of the class of all polygons with k vertices

(Asked by: username_0 on 2022-04-21)

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](https://cs.nyu.edu/%7Emohri/ml/ml08/sol2.pdf)) that VC dimension for this case is in fact also $2k + 1$. Any idea if this is correct?

**Tags:** machine-learning, computational-geometry, vc-dimension, pac-learning

> **Comments:**
> **username_1**: Which of Mohri’s arguments gives you indication that it’s 2k+1? I don’t see it.  
> **username_0**: Indeed, there's no argument in dat document, just a statement.  

---

## 1 answers

### Answer by username_1 on 2022-04-29. Score: 3

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.

> **Comments:**
> **username_0**: Thank you, username_1! I used the same lemma, but with a "convex partition by segments" - https://www.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.  
> **username_1**: Interesting, worth thinking about!  

---

