Thread: On Q9
View Single Post
Old 10-24-2012, 10:56 PM
yaser's Avatar
yaser yaser is offline
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: On Q9

Originally Posted by skyw2012 View Post
Trying to solve this question (sadly I failed) I realized that I didn't quite understand the shattering correctly in the beginning. In the meantime I've clarified this but still I don't know how to answer this question.
I imagine that must be a particular way of either selecting the right sets of points from the options of the question to prove they can be shattered or to identify the break point for this case to ensure that any set of points equal or greater can't be shattered.
Any suggestions on how to approach the solution? Thank you
There is no systematic way of doing this, but here are some tips.

The choice of where to place the points should be done so as to maximize the chances that they will be shattered. Since the triangle is a convex region, having one of the points being 'internal' to other points will preclude the possibility of shattering (same situation as in the case of convex regions discussed in the lecture). Therefore, choosing the points at the perimeter of a circle (for example) would be a good starting point.

Now, imagine all kinds of triangles trying to split these points into different dichotomies, and look for how many points you can afford to have while being able to split them in every possible way using triangles. It's an interesting puzzle to work on.
Where everyone thinks alike, no one thinks very much
Reply With Quote