Lower bounds for weak epsilon-nets and stair-convexity

ABSTRACT

A set N ⊂ R^d is called a weak ε-net (with respect to convex sets) for a finite X ⊂ R^d if N intersects every convex set C with |X ∩ C|≥ε|X|. For every fixed d≥ 2 and every r≥ 1 we construct sets X⊂ R^d for which every weak 1/r-net has at least Ω(r log^d-1 r) points; this is the first superlinear lower bound for weak ε-nets in a fixed dimension.

The construction is a stretched grid, i.e., the Cartesian product of d suitable fast-growing finite sequences, 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 R^d, d≥ 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 et al. (2008) are not far from the truth in the worst case.

Using the stretched grid we also improve the known upper bound for the so-called second selection lemma in the plane by a logarithmic factor: We obtain a set T of t triangles with vertices in an n-point set in the plane such that no point is contained in more than O l( t² / (n³ log n³/t ) r) triangles of T.

REFERENCES

• 1: . Alon, I. Bárány, Z. Füredi, and D. J. Kleitman. Point selections and weak ε-nets for convex hulls. Combin. Probab. Comput., 1:189--200, 1992.
• 2: . Alon, G. Kalai, J. Matousek, and R. Meshulam. Transversal numbers for hypergraphs arising in geometry. Adv. Appl. Math., 130:2509--2514, 2002.
• 3: Noga Alon , Haim Kaplan , Gabriel Nivasch , Micha Sharir , Shakhar Smorodinsky, Weak ε-nets and interval chains, Journal of the ACM (JACM), v.55 n.6, p.1-32, December 2008 [doi>10.1145/1455248.1455252]
• 4: . Alon and D. Kleitman. Piercing convex sets and the Hadwiger-Debrunner (p,q)-problem. Adv. Math., 96(1):103--112, 1992.
• 5: . Bárány, Z. Füredi, and L. Lovász. On the number of halving planes. Combinatorica, 10:175--183, 1990.
• 6: . G. Bradford and V. Capoyleas. Weak ε-nets for points on a hypersphere. Discrete Comput. Geom., 18:83--91, 1997.
• 7: . Bukh, J. Matousek, and G. Nivasch. Stabbing simplices by points and flats. Discrete Comput. Geom., to appear.
• 8: . Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, M. Sharir, and E. Welzl. Improved bounds on weak ε-nets for convex sets. Discrete Comput. Geom., 13:1--15, 1995.
• 9: David Eppstein, Improved bounds for intersecting triangles and halving planes, Journal of Combinatorial Theory Series A, v.62 n.1, p.176-182, Jan. 1993 [doi>10.1016/0097-3165(93)90082-J]
• 10: . Haussler and E. Welzl. ε-nets and simplex range queries. Discrete Comput. Geom., 2:127--151, 1987.
• 11: . Kirchberger. Über Tchebychefsche Annaherungsmethoden. Math. Ann., 57(4):509--540, 1903.
• 12: Evelyn Magazanik , Micha A. Perles, Staircase Connected Sets, Discrete & Computational Geometry, v.37 n.4, p.587-599, May 2007 [doi>10.1007/s00454-007-1308-9]
• 13: . Matousek. Geometric Discrepancy (An Illustrated Guide). Springer-Verlag, Berlin, 1999.
• 14: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 15: . Matousek. A lower bound for weak ε-nets in high dimension. Discrete Comput. Geom., 28:45--48, 2002.
• 16: Jirí Matousek , Uli Wagner, New Constructions of Weak ε-Nets, Discrete & Computational Geometry, v.32 n.2, p.195-206, July 2004 [doi>10.1007/s00454-004-1116-4]
• 17: Gabriel Nivasch, Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1-10, January 04-06, 2009, New York, New York
• 18: Gabriel Nivasch , Micha Sharir, Note: Eppstein's bound on intersecting triangles revisited, Journal of Combinatorial Theory Series A, v.116 n.2, p.494-497, February, 2009 [doi>10.1016/j.jcta.2008.07.003]
• 19: . F. Roth. On irregularities of distribution. Mathematika, 1:73--79, 1954.
• 20: . L. G. van de Vel. Theory of Convex Structures. North-Holland, 1993.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Theory

Keywords:
inverse ackermann function, selection lemma, stair-convexity, weak epsilon-net