# VC dimension of finite unions of one-sided intervals

What is the VC dimension of $k$ finite unions of one-sided intervals:

If we take 3 one-sided intervals like $(-\infty, a_1]$, $(-\infty, a_2]$ and $(-\infty, a_3]$, I think union of these intervals can shatter $4$ points as below, assuming that $a_1>a_2>a_3>a_4$:

• Point $p_1$ at interval $(-\infty, a_1]$

• Point $p_2$ at interval $[a_1, a_2]$

• Point $p_3$ at interval $[a_2,a_3]$

• Point $p_4$ at interval $(-\infty, a_3]$

For $k$ finite unions I think answer is $k+1$, am I right?

• Can you explain what you mean by "$k$ finite unions of one-sided intervals"? – Yuval Filmus Aug 27 '18 at 1:18
• @YuvalFilmus I mean union of $(-\infty, a1] U (-\infty, a2] U (-\infty, a3]$ – Joshna Gunturu Aug 27 '18 at 2:21
• This union is equal to $(-\infty, \max(a_1,a_2,a_3))$, that is, to a single interval. – Yuval Filmus Aug 27 '18 at 5:54
• Is $[a1,+\infty)$ also a one-sided interval? Can you copy and past the full original problem statement or provide an accessible link? As implied by Yuval Filmus, it is not easy to comprehend your paraphrase of the problem. By the way, the VC dimension of the subsets of the real line formed by the union of $k$ intervals is $2k$. – John L. Aug 28 '18 at 8:44