MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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?

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.