5
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Are the hyperplanes allowed to be affine? $\endgroup$ Jun 10, 2012 at 16:46
  • $\begingroup$ Yes, the hyperplanes are affine. $\endgroup$ Jun 10, 2012 at 23:26

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks! I also found Bernard Chazelle's `The discrepency method' to have the same proof on page 206. $\endgroup$ Jun 11, 2012 at 0:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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