1
$\begingroup$

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

Consider right-angle 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.

Claim is that the VC-dimension of the mentioned above hypothesis class is $VCdim(\mathcal{H})=4$. In order to prove it 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 stucked proving the second condition. I split the proof into three cases, which differs 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 a right-angled axis-aligned triangle.

Any help will be appreciated. Thank you.

New contributor
Dennis is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Your Answer

Dennis is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.