# Weak ε-nets and interval chains

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

Research output: Contribution to journalArticlepeer-review

20 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 language English (US) 28 Journal of the ACM 55 6 https://doi.org/10.1145/1455248.1455252 Published - Dec 1 2008 Yes

## 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.