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](http://en.wikipedia.org/wiki/VC_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?



Hyperplane arrangements and covering numbers
The Lemma follows from the Cutting lemma:
[J. Matousek, Lectures on Discrete Geometry, Theorem 6.5.3](http://kam.mff.cuni.cz/~matousek/dg.html).


This gives a partition of $\mathbb{R}^d$ into $O(k^d)$ generalized simplices (intersections of $d$ hyperplanes), each intersected by at most $n/k$ hyperplanes of $H$. To obtain the set $T(k)$, pick one point from each of the simplices.


