Small $\epsilon$-nets for points and half-planes without VC dimension 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 &gt; 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)?
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&#39;\subset \cal H$ be the set of $H\in\cal H$ that contain at least $\alpha |X|$ points of $X$, where $\alpha &gt; 0$ is to be determined. For a given $H\in {\cal H}$, the probability that it is in $\cal H&#39;$, 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&#39;$ has at most $r(r-1)$ members, by a union bound, the probability that every member of $\cal H&#39;$ 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.