Small $\epsilon$-nets for points and half-planes without VC dimension

Question

I have recently learned the proof of Haussler and Welzl of the following theorem.

Theorem. Suppose we have a set system $\mathcal{F} \subseteq 2^X$, where $X$ is a finite set. Suppose $\mathcal{F}$ has VC-dimension $d$. Then for every $\epsilon > 0$ there exists a hitting set ($\epsilon$-net) of size $O(\frac{d}{\epsilon} \log \frac{1}{\epsilon})$ of the following subfamily of $\mathcal{F}$: $\{F \in \mathcal{F} \mid |F| \geq \epsilon |X|\}$.

The proof itself is essentially a probabilistic argument. Despite its simplicity it looks very unnatural (we consider very mysterious coupling).

There is an interesting non-trivial case: suppose $X$ is a finite set of points in $\mathbb{R}^2$ and $\mathcal{F}$ is a family of subsets of $X$ which can be separated from their complements by half-planes. It is easy to check that in this case $d = 3$.

Is there a proof of the existence of a good $\epsilon$-net in this case from the first principles (without introduction of VC-dimension)?

Answer 1

For the particular case of points and half-planes, there is a simple (but a little tricky) argument that there is $R\subset X$ of size $r$ such that the supporting open half-planes of the convex hull of $R$ each contain at most $O(\log r)/r$ points of $X$. (Such half-planes are exactly the set of half-planes that are bounded by a line through two points of $R$ and contain no points of $R$.)

Also, any open half-plane that contains no points of $R$ is contained in two such supporting half-planes. (I won't give a proof of this.)

Therefore, $R$ is an $\epsilon$-net for a size $r$ which is $O(\log(1/\epsilon)/\epsilon$.

For the existence of such an $R$, suppose $R$ is a random sample of $X$ of size $r$, each member of $R$ chosen independently. Let $\cal H$ be the set of at most $r(r-1)$ open half-planes $H$ bounded by lines through two (or more) points of $R$, and let $\cal H'\subset \cal H$ be the set of $H\in\cal H$ that contain at least $\alpha |X|$ points of $X$, where $\alpha > 0$ is to be determined. For a given $H\in {\cal H}$, the probability that it is in $\cal H'$, and that none of the other $r-2$ points of $R$ falls in $H$, is at most $(1-\alpha)^{r-2}\le \exp(-\alpha(r-2))$. There is $\alpha = O(\log r)/r$ such that this probability is at most $1/2r(r-1)$. Since $\cal H'$ has at most $r(r-1)$ members, by a union bound, the probability that every member of $\cal H'$ contains a point of $R$ is at least $1/2$. So there is some $R$ such that every supporting half-plane of its convex hull contains at most an $\alpha = O(\log r)/r$ fraction of the points of $X$.

This sort of argument goes back to at least 1985, where $\epsilon$-net results were given for balls and halfspaces, and given in more generality in 1986, where results for $\epsilon$-nets and a kind of partial $\epsilon$-approximation were given. The set $\cal H$ above, a collection of half-planes defined by a set of points, is generalized to a collection of "regions" defined by a set of "objects", where the number of defining objects is typically a function of the dimension, but the simple union bound argument is the same. However, not all range spaces of bounded VC dimension fit in this framework.

Answer 2

The eps-net theorem is an easy consequence of the eps-sample/approximation theorem. The easiest way to prove the eps-sample theorem is probably via discrepancy. In this case, you can bound the number of ranges using direct geometric argument, so you do not need the VC dimension argument at all...

For a description of the eps-net theorem via discrepancy, see the book by Bernard Chazelle: http://www.cs.princeton.edu/~chazelle/book.html. Or the book by Jirka Matousek: http://kam.mff.cuni.cz/~matousek/di.html. It is also described in my book http://goo.gl/pLiEO (this is an early draft).

Answer 3

There is very easy "deterministic" proof which gives a better $\epsilon$-net: that is, of size $O(\frac{1}{\epsilon})$. You can find it here in Section 4.

The idea is the following: we build convex hull of $X$, and then find minimal $\epsilon$-net that consists only of points from the convex hull.

Answer 4

As pointed out in the answer by @ilyaraz, the question is easy for 2D points and halfplanes. It becomes much more interesting for 3D points and halfspaces. An $\epsilon$-net of size $O(\frac{1}{\epsilon})$ is still possible in the 3D case, but the proof requires much more work. Even the latest "simple" proof is actually surprisingly complex, bearing in mind the simplicity of the 2D case:

Evangelia Pyrga, Saurabh Ray. New Existence Proofs for epsilon-Nets. SoCG 2008. http://www.mpi-inf.mpg.de/~pyrga/e-nets.pdf

This paper also gives references to earlier proofs by Matousek et al.