<p>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...</p>

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

CC BY-SA 3.0
2011-09-24T16:33:37.203Z
2011-09-24T16:33:37.203Z
Sariel Har-Peled
<p>There is very easy "deterministic" proof which gives a better $\epsilon$-net: that is, of size $O(\frac{1}{\epsilon})$. You can find it <a href="http://dl.acm.org/citation.cfm?id=98529" rel="nofollow">here</a> in Section 4.</p>

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

CC BY-SA 3.0
2011-09-25T07:21:02.367Z
2011-09-25T07:32:53.933Z
2011-09-25T07:32:53.933Z
ilyaraz
<p>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:</p>

<p>Evangelia Pyrga, Saurabh Ray. New Existence Proofs for epsilon-Nets. SoCG 2008.
<a href="http://www.mpi-inf.mpg.de/~pyrga/e-nets.pdf" rel="nofollow">http://www.mpi-inf.mpg.de/~pyrga/e-nets.pdf</a></p>

<p>This paper also gives references to earlier proofs by Matousek et al.</p>

CC BY-SA 4.0
2022-07-14T23:32:49.347Z
For the record, there are at least 5 simpler proofs of this fact in 3d ;) :
https://arxiv.org/abs/1410.3154
Sariel Har-Peled
CC BY-SA 3.0
2011-09-26T23:20:33.957Z
2011-09-26T23:20:33.957Z
Alexander Tiskin
<p>For the particular case of points and half-planes, there is a simple (but a little tricky) argument that there is <span class="math-container">$R\subset X$</span> of size <span class="math-container">$r$</span> such that the supporting open half-planes of the convex hull of <span class="math-container">$R$</span> each contain at most <span class="math-container">$O(\log r)/r$</span> points of <span class="math-container">$X$</span>. (Such half-planes are exactly the set of half-planes that are bounded by a line through two points of <span class="math-container">$R$</span> and contain no points of <span class="math-container">$R$</span>.)</p>
<p>Also, any open half-plane that contains no points of <span class="math-container">$R$</span> is contained in two such supporting half-planes. (I won't give a proof of this.)</p>
<p>Therefore, <span class="math-container">$R$</span> is an <span class="math-container">$\epsilon$</span>-net for a size <span class="math-container">$r$</span> which is <span class="math-container">$O(\log(1/\epsilon)/\epsilon$</span>.</p>
<p>For the existence of such an <span class="math-container">$R$</span>, suppose <span class="math-container">$R$</span> is a random sample of <span class="math-container">$X$</span> of size <span class="math-container">$r$</span>, each member of <span class="math-container">$R$</span> chosen independently. Let <span class="math-container">$\cal H$</span> be the set of at most <span class="math-container">$r(r-1)$</span> open half-planes <span class="math-container">$H$</span> bounded by lines through two (or more) points of <span class="math-container">$R$</span>, and let <span class="math-container">$\cal H'\subset \cal H$</span> be the set of <span class="math-container">$H\in\cal H$</span> that contain at least <span class="math-container">$\alpha |X|$</span> points of <span class="math-container">$X$</span>, where <span class="math-container">$\alpha &gt; 0$</span> is to be determined. For a given <span class="math-container">$H\in {\cal H}$</span>, the probability that it is in <span class="math-container">$\cal H'$</span>, and that none of the other <span class="math-container">$r-2$</span> points of <span class="math-container">$R$</span> falls in <span class="math-container">$H$</span>, is at most <span class="math-container">$(1-\alpha)^{r-2}\le \exp(-\alpha(r-2))$</span>. There is <span class="math-container">$\alpha = O(\log r)/r$</span> such that this probability is at most <span class="math-container">$1/2r(r-1)$</span>. Since <span class="math-container">$\cal H'$</span> has at most <span class="math-container">$r(r-1)$</span> members, by a union bound, the probability that every member of <span class="math-container">$\cal H'$</span> contains a point of <span class="math-container">$R$</span> is at least <span class="math-container">$1/2$</span>. So there is some <span class="math-container">$R$</span> such that every supporting half-plane of its convex hull contains at most an <span class="math-container">$\alpha = O(\log r)/r$</span> fraction of the points of <span class="math-container">$X$</span>.</p>
<p>This sort of argument goes back to at least <a href="http://kenclarkson.org/pubs.html#rpo" rel="nofollow noreferrer">1985</a>, where <span class="math-container">$\epsilon$</span>-net results were given for balls and halfspaces, and given in more generality in <a href="http://kenclarkson.org/pubs.html#rs" rel="nofollow noreferrer">1986</a>, where results for <span class="math-container">$\epsilon$</span>-nets and a kind of partial <span class="math-container">$\epsilon$</span>-approximation were given. The set <span class="math-container">$\cal H$</span> above, a collection of half-planes defined by a set of points, is generalized to a collection of &quot;regions&quot; defined by a set of &quot;objects&quot;, 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.</p>

CC BY-SA 4.0
2011-09-24T20:56:04.460Z
2022-07-13T11:58:47.077Z
2022-07-13T11:58:47.077Z
Ken Clarkson
<p>I have recently learned the <a href="http://dl.acm.org/citation.cfm?id=10522">proof of Haussler and Welzl</a> of the following theorem.</p>

<p><strong>Theorem.</strong> Suppose we have a set system $\mathcal{F} \subseteq 2^X$, where $X$ is a finite set. Suppose $\mathcal{F}$ has <a href="http://en.wikipedia.org/wiki/VC_dimension">VC-dimension</a> $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|\}$.</p>

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

<p>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$.</p>

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

<co.combinatorics><cg.comp-geom><pr.probability><vc-dimension>
Small $\epsilon$-nets for points and half-planes without VC dimension
ilyaraz
# Small $\epsilon$-nets for points and half-planes without VC dimension

(Asked by: username_0 on 2011-09-24)

I have recently learned the [proof of Haussler and Welzl](http://dl.acm.org/citation.cfm?id=10522) 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](http://en.wikipedia.org/wiki/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)?**

**Tags:** co.combinatorics, cg.comp-geom, pr.probability, vc-dimension


---

## 4 answers

### Answer by username_3 on 2011-09-24. Score: 10 | Accepted answer

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](http://kenclarkson.org/pubs.html#rpo), where $\epsilon$-net results were given for balls and halfspaces, and given in more generality in [1986](http://kenclarkson.org/pubs.html#rs), 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 by username_1 on 2011-09-24. Score: 5

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 by username_0 on 2011-09-25. Score: 4

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](http://dl.acm.org/citation.cfm?id=98529) 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 by username_2 on 2011-09-26. Score: 3

As pointed out in the answer by @username_0, 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.

> **Comments:**
> **username_1**: For the record, there are at least 5 simpler proofs of this fact in 3d ;) : https://arxiv.org/abs/1410.3154  

---

