Prove that the VC dimension of rotatable squares in a plane is $5$.
Also, please look at the alternate statement below if not familiar with VC dimension:
Prove that for any set $S$ of six points on a plane, there is a subset $T\subset S$, such that there is no square (closed, with interior, not necessarily axis-aligned) such that all the points in $T$ are covered by the square, while all the points in $S\backslash T$ are not covered by the square.
This is a homework problem for my friend (I asked him, and he said that it is okay to post on the internet). It is trivial to find five points to be shattered, but both he and I are unable to solve for six points…. For six points, I have tried to find the diameter of the point set and try to first rule out the possibility of there existing points on both sides. Also, there is a trivial discovery: the example, if exists, must be a convex hexagon.
I tried to search the internet and found that the problem also appears in course E0 290: Mathematical Foundations for Modern Computing (Jan–Apr 2011) of Indian Institute of Science. However, I could not open the lecture note link…. Nor I could search the Hopcroft–Kannan book it mentioned. So, I could confidently say that the correctness for this problem is guaranteed, but I could not find the solution… any solution and hints are welcome.
P.S. I think it would be helpful to give the example of five points: $(100,0)$, $(-100,0)$, $(-50,-51)$, $(50,-51)$ and $(0,-52)$. The construction is following the idea that it is better to put all the points on the same side of the diameter.
P.P.S. The TA for that homework does not have the solution either….
P.S.3 I can now open the lecture note of that course. However, it does not seem to be helpful to solve this problem, and the lecture notes do not contain any answer.