Weak ε-nets and interval chains Academic Article uri icon


  • We construct weak e-nets of almost linear size forcertain types of point sets. Specifically, for planar point sets inconvex position we construct weak 1/r-nets of size O(rα(r)),where α(r) denotes the inverse Ackermann function. For pointsets along the moment curve in ℝ d we constructweak 1/r-nets of size r · 2 poly(α(r)) ,where the degree of the polynomial in the exponent depends(quadratically) on d. Our constructions result from a reduction to a new problem,which we call stabbing interval chains with j-tuples. Given therange of integers N = [1, n], an interval chain of length k is asequence of k consecutive, disjoint, nonempty intervals containedin N. A j-tuple $\bar{P}$ = (p1,…,pj) is said to stab aninterval chain C = I 1 …I k if eachp i falls on a different interval of C. The problem is toconstruct a small-size family Z of j-tuples that stabs allk-interval chains in N. Let z (j) k (n) denote the minimum size ofsuch a family Z. We derive almost-tight upper and lower bounds forz (j) k (n) for every fixed j; our boundsinvolve functions α m (n) of the inverse Ackermannhierarchy. Specifically, we show that for j = 3 we havez (3) k (n) =Θ(nα $\lfloor$k/2$\rfloor$ (n)) for all k ≥6. For each j≥4, we construct a pair of functionsPʹ j (m), Qʹ j (m), almost equalasymptotically, such that z (j) Pʹ j(m)(n)= O(nα m (n)) andz (j) Qʹ j(m)(n) =Ω(nα m (n)).

publication date

  • January 1, 2008