Skip to main content
1 of 5
Cain
  • 393
  • 1
  • 11

Vapnik-Chervonenkis dimension of lines in the plane

I'm having some problems with this problem concerning VC dimensions, I hope for some helping input.

Given a set L of n lines in the plane, define a hypergraph H=(L,S) such that its vertices are the lines and a subset l of L belongs to S iff there exist points p and q such that all lines in l lie between p and q, what is the VC dimension of H?

Now, I've managed to show the VC dimension is at least 5, but I can't think of a solid proof why it shouldn't be more than 5 (it might be more, its a bit confusing to me).

Thanks a lot.

Cain
  • 393
  • 1
  • 11