2
$\begingroup$

It can be shown that VC dimension of rotatable rectangles is 7.

The problem is I cannot understand how to approach the solution. So far I used bruteforce to solve this kind of problem, I was drawing points in different shapes and check whenever the hypothesis shatters the points. In this case the heptagon is the key. In solution it's mentioned that it's easy to show that 0,1,2,6,7 points can be shattered, except for bruteforce "drawing" I don't know any other way to show this. And the case with 3 is considered separately.

I would appreciate if someone could explain why case with 0,1,2,6,7 can be shown easily and 3 needs special treating.

Is there are any reason why 8 doesn't work here.

$\endgroup$

1 Answer 1

2
$\begingroup$

0 - draw a rectangle outside the heptagon

1 - draw rectangles separately around each point

2 - draw rectangles taking every 2 point ($^{7}C_{2}$) combination

5 - the classes of rectangles can be easily devised in the same fashion as for 3 and 4 in the resource referenced by @user16168

6 - rectangle leaving one point (7 different ones, leaving one each time)

7 - rectangle enclosing all points

3,4( and 5) are non trivial cases and have been discussed in the resource referenced by @user16168. 5 would follow on similar lines as 3 and 4.

In the case of 8 points, ie. in an octagon, you would not be able to draw rectangles for 5 points. However this statement in isolation does not imply VC dimension of rotatable rectangles is 7. One would need to prove that, rotatable rectangles cannot shatter any combination of 8 points. I am not sure how the proof would look like. Probably somebody else can add on.

Update:

An easy way I recently found is to use the Convex Hull (CH) method. Say you want to check for an axis parallel rectangle. Its VC dim is 4. To check for 5 points, put them all on the rectangle(boundary). Then there's no way you can draw rectangles for all combinations of 4 points. In the other case when at least one point is not on the CH, there's no way to draw a rectangle excluding all points not on the CH. Hence a rectangle cannot "shatter" any set of more than 5 points.

This can be extended to many geometric shapes and is considerably general.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .