# Hyperplane arrangements and covering numbers

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?

-
Are the hyperplanes allowed to be affine? – Vidit Nanda Jun 10 '12 at 16:46
Yes, the hyperplanes are affine. – Robby McKilliam Jun 10 '12 at 23:26

The Lemma follows from the Cutting lemma: J. Matousek, Lectures on Discrete Geometry, Theorem 6.5.3.

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.

-
Thanks! I also found Bernard Chazelle's The discrepency method' to have the same proof on page 206. – Robby McKilliam Jun 11 '12 at 0:28