Skip to main content
2 of 5
improved latex formatting
MTS
  • 8.6k
  • 2
  • 35
  • 65

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