VC Dimension of star-shaped sets on $\mathbb{R}^2$ Consider a set $U \subset \mathbb{R}^2$ to be star-shaped with respect to
a point $\epsilon \in \mathbb{R}^2$ if for every $x \in U$, the segment
joining $\epsilon$ and $x$ is contained in $U$.
Consider the $H = \{U \subset \mathbb{R}^2 | U \text{ is starshaped with
respect to } \epsilon, \epsilon \in \mathbb{R}^2\}$ And take
$H_{+}$ to be all the hypotheses in $H$ that assign $1$ if $x$ is within
the starshaped set and $0$ otherwise. I am interested in finding
the VC dimension of $H$. I have a feeling that this can account for an
infinite number of points on $\mathbb{R}^2$, but I am having trouble
formalizing this proof. Many of my friends said that these problems are
best answered using "matrix" methods over all dichotomies of my observations.
Is there a better method for handling this?


Lemma. The set system $(\mathbb{R}^2, H_\epsilon)$, where $H_\epsilon = \{U \subset \mathbb{R}^2 \mid U$ is star-shaped with respect to $\epsilon\}$, has infinite VC-dimension.

The idea to prove the lemma is to find a set $S \subset \mathbb{R}^2$ of size $s$ that can be shattered by $H_\epsilon$, for arbitrary $s$. For $\forall s$, we construct $S$ as follows:


*

*Select $s$ distinct points from $\{p \in \mathbb{R}^2\mid \|p - \epsilon\|_2 = 1\}$. That is, select $s$ distinct points from the unit circle centered at $\epsilon$.


For any subset $T$ of $S$ above, we define a star-shaped set $U_T$ as follows:
$$
U_T = \{p \in \mathbb{R}^2 \mid p\text{ is on a segment joining $\epsilon$ and $v$ for some $v\in T$}\}
$$
It is easy to observe that $U_T \in H_\epsilon$ and additionally, $T = S \cap U_T$. Therefore, $S$ constructed above can be shattered by $H_\epsilon$.
