A non-linear lower bound for planar epsilon-nets

CSCE 669Project Presentation (Paper Reading)Student Presenter:Praveen TiwariOriginal Author:Noga Alon, TelAviv UniversityPublication:FOCS'10 Proceedings of the 2010 IEEE 51stAnnual Symposiumon Foundationsof ComputerScience
A non-linear lower bound for planar epsilon-nets
What is an epsilon-net?
Intuitive Idea:Given a(finite) setX of n points in ℛ2, can we find asmall(sayf(n,ε)) P⊆X, so that any triangleT⊆ℛ2coveringsome points in X(≥εn)contains atleast one point in P?That is, wesomehow want to approximate the larger set X by a subset P satisfying some property
What is an epsilon-net?
Formal Definition:Range Space:S:(X,ℛ) for a (finite) set X of points (objects) and ℛ (range) is a set of subsets of XVC(Vapnik-Chervonenkis)-dimension:A set A⊆X is shattered by ℛ if ∀B⊂A,∃R∊ℛs.t.R⋂A= BVC(S)= sup {|A|| A⊆X is shattered}ε-Net:A subset N⊂A, s.t. ∀ R∊ℛ, and0<ε<1, |R⋂A|≥ε|A| andR⋂N≠Ø
Bounds on epsilon-nets
Question:For a given range space S(X,ℛ) with aVC-dimensiond in a geometric scenario, what is the lower bound on size of ε-net?Haussler and Welzl:For any n and ε>0, any set of size n in a range space ofVC-dimensiond contains an ε-net of size at most O((d/ε)log(1/ε))Is this bound tight?Lower Bound:There is no natural geometric example where size of smallest ε-net is better than trivial Ω(1/ε)Question:Whether or not in all geometric scenarios of VC-dimension d, there exists an ε-net of size O(d/ε)? (Matousek, Siedel and Welzl)
Previous Work
Linear upper bounds have been established for special geometric cases, like point objects and half space ranges in 2D and 3DPach, Woeginger: For d=2, there exist range spaces that require nets of size Ω(1/ε log(1/ε))(no geometric scenario)
Contributions
The linear bound on size of ε does not hold, not evenin verysimple geometric situations (VC-dimension=2)The minimum size of such an ε-net is Ω((1/ε)ω(1/ε)) whereωis inverse Ackermann'sfunction with respect to lines, i.e.forVC-dimension= 2Using VC dimension = 2:Two theorems on strong ε-netsOne theorem on weak ε-nets
Results
Theorem 1:For every (large) positive constant C there exist n and ε > 0 and a set X of n points inthe plane,so that the smallest possible size of an ε-net for lines of X is larger that C·(1/ε)Def.: Afat linein a plane is the set of all points within distanceμfrom a line in the plane.Theorem 2:For every (large) positive constant C there exists a sequence εiof positive reals tending to zero, so that for every ε=εiin the sequence and for all n > n0(εi) there exists a set Ynof n points in general position in the plane, so that the smallest possible size of an ε-net for fat lines for Ynis larger than C·(1/ε)
Results
Weak ε-nets:A relaxation to Strong ε-netsDef.:For a finite set of points X in ℛ, given A⊂X, a subset N⊂R is aweak ε-netif∀R∊ℛ, and 0<ε<1, |R⋂A| ≥ε|A| and R⋂N≠∅The difference is that the set N need not be a subset of A asearlierTheorem3:For every (large) positive constant C there exist n and ε>0 and a set X of n points in the plane, so that the smallest possible size of a weak ε-net for lines for X is larger than C·(1/ε)
Proofs
Proofs use a strong result byFurstenbergand Katznelson, known as the density version of Hales-Jewett Theorem.Def.:For an integerk≥ 2, let [k]={1,2,...,k} and let [k]ddenote the set of all vectors of lengthdwith coordinates in [k]. Acombinatorial lineis a subsetL⊂ [k]dso that there is a set of coordinatesI⊂ [d] = {1,2,...,d},I≠ [d], and valueski∊ [k] fori∊Ifor whichLis the following set ofkmembers of [k]d:L={l1,l2,...,lk}wherelj={(x1,x2,...,xd)}:xi= kifor alli∊Iandxi= jfor alli∊[d]\I}
Proofs
Density Hales-Jewett Theorem (Furstenbergand Katznelson):For any fixed integer k and any fixed δ > 0 there exists an integer d0= d0(k,δ) so that for any d ≥ d0, any set Y of at least δkdmembers of [k]dcontains a combinatorial line.Construction(forTheorem1):Every combinatorial line in X=[k]dis a line inℛd. If d = d0(k,1/2) and n=kd, ε=k/kd, then any ε-net with respect to lines must be of size ≥ (k/2)(1/ε)Now for planar construction, project these combinatorial lines randomly onℛ2Othertwo theorems use similar constructions with simple modifications
Conclusions
The conjecture that minimum size of epsilon net is linearly bounded by (1/ε) is not true for geometric examples in VC-dimension = 2 for both strong as well as weak ε-nets.This paper only proves that the bounds are not linear, but whether there are natural examples for an Ω ((d/ε)log(1/ε)) lower bound for range spaces of VC dimension d, is still open.Recent Work:Pach and Tardos proved that there are geometric range spaces of VC-dimension 2 in which the minimum possible size of an ε-net is Ω ((1/ε)log(1/ε)). Their method does not seem to provide any non-linear bounds for weakε-nets.
Bibliography
Alon N., A non-linear lower bound for planar epsilon-nets, FOCS 2010Alon N., Web Seminars, Isaac Newton Institute for Mathematical Sciences, Jan 11, 2011H. Furstenberg and Y.Katznelson, A density version of the Hales-Jewett theorem, J. Anal.Math. 57(1991),64-119D. Haussler andE.Welzl,ε-netsand simplex range queries, Discrete and ComputationalGeometry 2(1987),127-151J.Pachand G.Woeginger, Some new bounds forε-nets, Proc. 6-th Annual Symposium on Computational Geometry, ACM Press, New York (1990), 10-15J.Matousek, R. Seidel and E.Welzl, How to net a lot with little: Small -nets for disks andhalfspaces, In Proc. 6thAnnu. ACMSympos.Comput. Geom., pages 16-22, 1990