Small $\epsilon$-nets for points and half-planes without 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.