We show that the minimum possible size of an ε-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in 1/ε. This settles a problem raised by Matoušek, Seidel and Welzl (Proc. 6th Annu. ACM Sympos. Comput. Geom., pp. 16-22, 1990).
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Epsilon nets
- Weak epsilon nets