Weak ε-nets and interval chains

Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky

Research output: Contribution to journalArticle

15 Scopus citations

Abstract

We construct weak ε-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1 r -nets of size O(rα(r )), where alpha;(r ) denotes the inverse Ackermann function. For point sets along the moment curve in Rd we construct weak 1 r -nets of size r poly(alpha;(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 the range of integers N = [1, n], an interval chain of length k is a sequence of k consecutive, disjoint, nonempty intervals contained in N. A j -tuple p = (p1, . . . , pj ) is said to stab an interval chain C = I1 Ik if each pi falls on a different interval of C. The problem is to construct a small-size family Z of j -tuples that stabs all k-interval chains in N. Let z( j )k (n) denote the minimum size of such a family Z. We derive almost-tight upper and lower bounds for z( j ) k (n) for every fixed j ; our bounds involve functions αm(n) of the inverse Ackermann hierarchy. Specifically, we show that for j = 3 we have z(3)k (n) = (equation given) for all k ≤ 6. For each j ≤ 4, we construct a pair of functions P' j (m), Q' j (m), almost equal symptotically, such that z( j ) P' j (m)(n) = O(nαm(n)) and z( j ) Q' j (m)(n) = Φ(nαm(n)).

Original languageEnglish (US)
Article number28
JournalJournal of the ACM
Volume55
Issue number6
DOIs
StatePublished - Dec 1 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Interval chain
  • Inverse Ackermann function
  • Moment curve
  • Weak epsilon-net

Fingerprint Dive into the research topics of 'Weak ε-nets and interval chains'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Kaplan, H., Nivasch, G., Sharir, M., & Smorodinsky, S. (2008). Weak ε-nets and interval chains. Journal of the ACM, 55(6), [28]. https://doi.org/10.1145/1455248.1455252