VC-Dimension of Axis-Aligned Right Triangles and 5-point Convex Hull

Question

I am having trouble proving the following fact about the VC dimension of triangles.

Consider axis-aligned right triangles in the plane, with the the right angle in the lower left corner.

The hypothesis in our case assigns label $1$ for points inside the triangle and label $0$ otherwise.

The claim is that the VC-dimension of the mentioned above hypothesis class is $VCdim(\mathcal{H})=4$. In order to prove it we need to show the following:

1. There is a set of cardinality 4 shattered by $\mathcal{H}$, and
2. Any set of cardinality greater than 4 is not shattered by $\mathcal{H}$. In other words, a set of cardinality $5$ cannot be shattered.

The first condition is easy. It suffices to give an example of 4 points in the plane, with any labeling, and show a triangle that covers the labeled points.

I am stuck proving the second condition. I split the proof into three cases, which differ by the amount of points that lay inside the convex hull created by those 5 points. The problem is with the case where none of those points lay inside the convex hull (i.e. they create a convex set).

I want to prove that for any combination of those 5 points that lay on a convex hull, there is a labeling that cannot be shattered by an axis-aligned right triangle.

Answer 1

In the case of a convex hull of 5 points you can select the smallest triangle T that contains all the 5 points.

Case 1: at least one point is inside that triangle

Simply label the inside points as 0 and the other as 1 and you will have that the smallest right triangle possible contains the 0 label points and therefore any other right triangle that contains the positive class contains the negative aswell.

Case 2: all the points are on the border of that smallest triangle, in particular each one of the three sides of the triangle has a point on it. You have two cases (either 2 points or more on a cathetus (one at least not in a corner) or three points or more on the hypotenuse)

Case 2-1 : three points aligned on the hypotenuse

Simply select the mid point as negative class and the rest of the 4 points as positive class. T is still the smallest triangle that is contained in all the possible traingles containing the positive class since removing that point does not change the convex hull of the other four and the 4-convex hull has to be inside the triangle.

Case 2-2: two points on a cathetus (one at least not in a corner)

Select the point not in the corner as negative and the 4 remaining as a positive class. The point removed does not change T as the minimum triangle containing the 4 other points since an axis aligned traingle just need the other 2 points one on each catetus select the right angle interception in the bottom left corner. the two points still determine the xmin and ymin and the unique triangle (passing between two points and right angle between them fixed) drawed.