Thread: Question 9 View Single Post
#4
 Elroch Invited Guest Join Date: Mar 2013 Posts: 143 Re: Question 9

Quote:
 Originally Posted by jlaurentum I failed question 9 because my concept of "shattering" was erroneous. A data set of size 1 can be shattered by the triangle hypothesis set. I have not worked on justifying the right answer for this question yet, but I suppose the way to go about it would be to take the sucessive values (k=1,3,5 and so on) and see if you can choose a set of points of size k so that all dichotomies are possible. For me though, it gets a little tricky to verify that for ANY given set of k points, not all dichotomies are possible.
Well, since a triangle is a convex set, if triangles can shatter the points, none of them is in the convex hull of the rest. That implies that the points are the vertices of a convex polygon. If you consider the intersection of a triangle with such a convex polygon, its border consists partly of a subset of the border of the convex polygon and partly of parts of the sides of the triangle.

This puts a strong constraint on the way that the points are divided up by such a triangle hypothesis, if you think of the points as being connected to the ones to the left and the right in the polygon. This is enough to get the exact value of the minimum break point.

I have to admit it took me quite a while to tie this argument together.