Title :
A Non-linear Lower Bound for Planar Epsilon-Nets
Author_Institution :
Schools of Math. & Comput. Sci., Tel Aviv Univ., Tel Aviv, Israel
Abstract :
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 Matousek, Seidel and Welzl in 1990.
Keywords :
computational geometry; ϵ-net; nonlinear lower bound; planar epsilon-nets; Approximation algorithms; Color; Computer science; Poles and towers; Polynomials; Vectors; Epsilon nets; VC dimension; weak epsilon nets;
Conference_Titel :
Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on
Conference_Location :
Las Vegas, NV
Print_ISBN :
978-1-4244-8525-3
DOI :
10.1109/FOCS.2010.39
