I need to prove the following:
Let $δ > 0$ Let $P$ be a finite set of n points in $\mathbb{R}^d$.
We say that a pair of open discs $D, D'\in \mathbb{R}^d$ are $δ$-separated (with respect to P) if the symmetric difference:
$D\Delta D':= (D$ \ $D') \cup (D'$ \ $D)$
contains at least $δn$ points of $P$.
Let $S$ be a set of open discs in $ \mathbb{R}^d$ so that any two of them are $δ$-separated (with respect to $P$). Show that $|S| = O((\frac1δ\log{\frac1\delta})^{d+2})$
(where the constants of proportionality do not depend on $δ > 0$
--
My thoughts were first to define two range spaces:
- $(\mathbb{R}^d,D)$ - where D is a set of all the open disks in $\mathbb{R}^d$
- $(\mathbb{R}^d,D_\text{sym})$ - where $D_\text{sym}$ is a set of all {$d\Delta d'$ | $d,d' \in D$}
Then show that $VC_\text{dim}(\mathbb{R}^d,D) = d+2$ and that $VC_\text{dim}(\mathbb{R}^d,D_\text{sym}) = O(1)$ And then use the $\epsilon-net$ lemma.
I've been having trouble proving the steps, and would appreciate some thoughts on how to prove them and how to proceed from there:)
$\epsilon-net$ Lemma: For any range space with finite VC dimension d, regardless of the choice of P, there exists an ε-net of P of size: $O(\frac d\epsilon\log{\frac d\epsilon})$