Access Restriction

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

   Open content in new tab
Source: ACM Digital Library