Abstrakt
A set N SUBSET OF ℝ d is called a weak ɛ-net (with respect to convex sets) for a finite X SUBSET OF ℝ d if N intersects every convex set C with |X INTERSECTION C| GREATER-THAN OR EQUAL TO ɛ|X|. For every fixed d GREATER-THAN OR EQUAL TO 2 and every r GREATER-THAN OR EQUAL TO 1 we construct sets X SUBSET OF ℝ d for which every weak 1/r -net has at least Ω(r log dMINUS SIGN 1 r) points; this is the first superlinear lower bound for weak ɛ-nets in a fixed dimension.
The construction is a stretched grid, and convexity in this grid can be analyzed using stair-convexity, a new variant of the usual notion of convexity. We also consider weak ɛ-nets for the diagonal of our stretched grid in ℝ d , d GREATER-THAN OR EQUAL TO 3, which is an "intrinsically 1-dimensional" point set.
In this case we exhibit slightly superlinear lower bounds (involving the inverse Ackermann function), showing that the upper bounds by Alon, Kaplan, Nivasch, Sharir and Smorodinsky (2008) are not far from the truth in the worst case. Using the stretched grid we also improve the upper bound for the so-called second selection lemma in the plane by a logarithmic factor.