Skip to main content
3 of 5
edited tags
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

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