New constructions of weak epsilon-nets

ABSTRACT

A finite set ? ? R^d is a weak e-net for an n -point set X ? R ^d (with respect to convex sets) if N intersects every convex set K with | K n X |= en. We give an alternative, and arguably simpler, proof of the fact, first shown by Chazelle et al. [7], that every point set X in R ^d admits a weak e-net of cardinality O (e ^-d polylog(1/e)). Moreover, for a number of special point sets (e.g., for points on the moment curve), our method gives substantially better bounds. The construction yields an algorithm to construct such weak eps-nets in time O ( n ln(1e)). We also prove, by a different method, a near-linear upper bound for points uniformly distributed on the (d--1)-dimensional sphere.

REFERENCES

• 1: K. Agarwal and Jivri Matouaek. On range searching with semialgebraic sets. Discrete Comput. Geom., 11:393--418, 1994.
• 2: Noga Alon, Imre Barany, Zoltan Füredi, and Daniel Kleitman. Point selections and weak e-nets for convex hulls. Combin. Probab. Comput., 1(3):103--112, 1992.
• 3: Noga Alon and Daniel J. Kleitman. Piercing convex sets and the Hadwiger-Debrunner (p,q)-problem. Adv. Math., 96(1):103--112, 1992.
• 4: Boris Aronov , Marco Pellegrini , Micha Sharir, On the zone of a surface in a hyperplane arrangement, Discrete & Computational Geometry, v.9 n.2, p.177-186, 1993 [doi>10.1007/BF02189317]
• 5: Jacek Bochnak, Michel Coste, and Marie Françoise Roy. Real Algebraic Geometry. Springer-Verlag, New York, 1998.
• 6: Bernard Chazelle, Herbert Edelsbrunner, David Eppstein, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, and Emo Welzl. Algorithms for weak epsilon-nets. Manuscript, 1995, available at http://citeseer.nj.nec.com/24190.html.
• 7: Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas J. Guibas, Micha Sharir, and Emo Welzl. Improved bounds on weak e-nets for convex sets. Discrete Comput. Geom., 13:1--15, 1995.
• 8: Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A Singly-Expenential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.179-193, July 11-15, 1989
• 9: David Haussler and Emo Welzl. e-Nets and Simplex Range Queries. Discrete Comput. Geom., 2:127--151, 1987.
• 10: V. Koltun (Machtey Award Co-winner), Almost Tight Upper Bounds for Vertical Decompositions in Four Dimensions, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.56, October 14-17, 2001
• 11: Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
• 12: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 13: Jivri Matouaek. A lower bound for weak e-nets in high dimension. Discrete Comput. Geom., 28:45--48, 2002.

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

General Terms:
Algorithms, Theory

Keywords:
weak epsilon-nets