<p>What would be a good source for open problems for (weak) epsilon nets? Is there a good survey/article that summarizes the recent advancements on the topic?</p>

CC BY-SA 3.0
2011-05-04T18:54:37.190Z
For those who do not know what weak ε-nets are (like me), see [Wikipedia](http://en.wikipedia.org/wiki/%CE%95-net_%28computational_geometry%29) and [Gil Kalai’s blog post](http://terrytao.wordpress.com/2007/04/22/gil-kalai-the-weak-epsilon-net-problem/).  Confusingly, they are sometimes also called ε-nets, although [ε-nets of metric spaces](http://en.wikipedia.org/wiki/%CE%95-net_%28metric_spaces%29) have a very different meaning.
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-06T04:10:40.593Z
The latest breakthroughs are apparently from 2010: Alon (A non-linear lower bound for planar epsilon-nets - http://www.tau.ac.il/~nogaa/PDFS/epsnet3.pdf) and Pach and Tardos (Tight lower bounds for the size of epsilon-nets - http://arxiv.org/PS_cache/arxiv/pdf/1012/1012.1240v1.pdf)
Sergiu
<reference-request><co.combinatorics><cg.comp-geom><lg.learning><epsilon-nets>
Open problems on epsilon nets
Sergiu
# Open problems on epsilon nets

(Asked by: username_0 on 2011-05-04)

What would be a good source for open problems for (weak) epsilon nets? Is there a good survey/article that summarizes the recent advancements on the topic?

**Tags:** reference-request, co.combinatorics, cg.comp-geom, lg.learning, epsilon-nets
> **Comments:**
> **username_1**: For those who do not know what weak ε-nets are (like me), see [Wikipedia](http://en.wikipedia.org/wiki/%CE%95-net_%28computational_geometry%29) and [Gil Kalai’s blog post](http://terrytao.wordpress.com/2007/04/22/gil-kalai-the-weak-epsilon-net-problem/).  Confusingly, they are sometimes also called ε-nets, although [ε-nets of metric spaces](http://en.wikipedia.org/wiki/%CE%95-net_%28metric_spaces%29) have a very different meaning.  
> **username_0**: The latest breakthroughs are apparently from 2010: Alon (A non-linear lower bound for planar epsilon-nets - http://www.tau.ac.il/~nogaa/PDFS/epsnet3.pdf) and Pach and Tardos (Tight lower bounds for the size of epsilon-nets - http://arxiv.org/PS_cache/arxiv/pdf/1012/1012.1240v1.pdf)  

---

## 0 answers

