Let $H$ be a set of $(d-1)$-dimensional hyperplanes in $\mathbb{R}^d$. For each hyperplane $h \in H$ let $D(h)$ and $\bar{D}(h)$ be the corresponding half spaces of $\mathbb{R}^d$. For a point $x \in \mathbb{R}^d$, define the function $$ b(h,x) = \begin{cases} 1 & x \in D(h) \\\ 0 & \text{otherwise}. \end{cases} $$ For points $x,y \in \mathbb{R}^d$, define the psuedometric, $$ \sigma(x,y) = \sum_{h \in H} |b(h,x) - b(h,y)|. $$ So $\sigma(x,y)$ counts the number of hyperplanes in $H$ that pass between the points $x$ and $y$. I believe that the following lemma is true, but have not yet found a proof.
Lemma
Let $N$ be the number of hyperplanes in $H$. There exists a polynomial $p$ (depending perhaps on $d$, but not on $N$) such that, for every positive integer $k$, there is a discrete subset $T(k) \subset \mathbb{R}^d$ containing not more than $p(k)$ elements with the property that for every $x$ in $\mathbb{R}^d$ there is a point $y \in T(k)$ with $\sigma(x,y) < \frac{N}{k}.$
Another way to state the Lemma is: We require at most $p(k)$ `balls' of radius $\frac{N}{k}$ (with respect to the metric $\sigma$) to cover $\mathbb{R}^d$.
The Lemma is related to what is called Vapnik–Chervonenkis dimension, and it arises when trying to prove results about certain empirical processes. I suspect this result (or something equivalent) to be in the literature, but I have not yet been able to dig it out.
Has anybody seen this result (or something equivalent) before? Alternatively, does anybody know a nice proof?
