Thread: Question 9
View Single Post
Old 04-24-2013, 02:28 PM
Elroch Elroch is offline
Invited Guest
Join Date: Mar 2013
Posts: 143
Default Re: Question 9

Originally Posted by jlaurentum View Post
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 2^k 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 k points, none of them is in the convex hull of the rest. That implies that the k 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 k points are divided up by such a triangle hypothesis, if you think of the k 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.
Reply With Quote