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?

Brittney
  • 169
  • Not sure what is meant by "hypotheses"-- so is $H_+$ to be the collection of characteristic functions for all sets $U$ which are star-shaped w.r.t. $\epsilon$? [Also I assume you intend $\epsilon$ to be a fixed point for the entire problem, is that right?] – coffeemath Jun 09 '16 at 23:25

1 Answers1

0

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$.

PSPACEhard
  • 10,283