Exercise 4.16: VC Dimension of Polygons

chapter 4

Take a regular nonagon inscribed to a circle, and and \(x_1\) to \(x_9\) to be its nine vertices. Observe that different labelings of these points can be represented by 4-gons inscribed to the circle on which the nonagon lies. Importantly, whenever any point and its clockwise¹ neighbour are to have a different label, one side of the 4-gon has to be placed between them. In other words, only the assignments in which the number of points with clockwise neighbour of different label is less than four are realisable by 4-gons in \(\R^2\). We will therefore be able to shatter all the \(2 \cdot 4 + 1 = 9\) points, where the \(+1\) comes from the fact that the \(9^\text{th}\) point will always have the same label as one of its neighbours, and thus we can treat it as the \(1^\text{st}\) point instead when needed.

An analogous argument shows that we can shatter at most \(9\) points which lie on a circle (to which the regular nonagon is inscribed), or more generally lie on the convex hull of all the points. Hence the only remaining way for more than 9 points to be shattered by 4-gons in \(\R^2\) is for at least one point \(x\) to lie inside the convex hull. However, then there will be a labelling which assigns \(0\) to \(x\) and \(1\) to at least two points from which \(x\) can be obtained by convex combination. Separating these three points will require two sides of the polygon; the remaining seven points can then be assigned an alternating \(0\)–\(1\) pattern which together with the two sides used to separate \(x\) from the other two points cannot form a 4-gon.