Publications: 73 | Followers: 0

A non-linear lower bound for planar epsilon-nets

Publish on Category: Birds 0

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)
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
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/ε)
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 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}
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
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.
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





Make amazing presentation for free
A non-linear lower bound for planar epsilon-nets