### Weak ε-nets and interval chainsWeak ε-nets and interval chains

Access Restriction
Subscribed

 Author Alon, Noga ♦ Kaplan, Haim ♦ Nivasch, Gabriel ♦ Sharir, Micha ♦ Smorodinsky, Shakhar Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2008 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Interval chain ♦ Inverse Ackermann function ♦ Moment curve ♦ Weak epsilon-net Abstract We construct weak ε-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)).$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2008-12-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 55 Issue Number 6 Page Count 32 Starting Page 1 Ending Page 32

#### Open content in new tab

Source: ACM Digital Library