New existence proofs ε-nets

ABSTRACT

We describe a new technique for proving the existence of small μ-nets for hypergraphs satisfying certain simple conditions. The technique is particularly useful for proving o(1/μ log 1/μ) upper bounds which the standard VC-dimension theory does not allow. We apply the technique to several geometric hypergraphs and obtain simple proofs for the existence of O(1/μ) size μ-nets for them. This includes the geometric hypergraph in which the vertex set is a set of points in the plane and the hyperedges are defined by a set of pseudo-disks. This result was not known previously. We also get a very short proof for O(1/μ) size μ-nets for half-spaces in R³.

REFERENCES

• 1: Pankaj K. Agarwal , Eran Nevo , János Pach , Rom Pinchasi , Micha Sharir , Shakhar Smorodinsky, Lenses in arrangements of pseudo-circles and their applications, Journal of the ACM (JACM), v.51 n.2, p.139-186, March 2004 [doi>10.1145/972639.972641]
• 2: Pankaj K. Agarwal, János Pach, and Micha Sharir. State of the union, of geometric objects: A review. manuscript, 2007.
• 3: Pankaj K. Agarwal , Micha Sharir, Pseudo-line arrangements: duality, algorithms, and applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.800-809, January 06-08, 2002, San Francisco, California
• 4: Martin Anthony , Norman Biggs, Computational learning theory: an introduction, Cambridge University Press, New York, NY, 1992
• 5: Claude Berge. Hypergraphs. page 256, 1989.
• 6: Hervé Brönnimann and Michael T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete & Computational Geometry, 14(4):463--479, 1995.
• 7: Marek Chrobak , David Eppstein, Planar orientations with low out-degree and compaction of adjacency matrices, Theoretical Computer Science, v.86 n.2, p.243-266, Sept. 2, 1991 [doi>10.1016/0304-3975(91)90020-3]
• 8: Kenneth L. Clarkson. Randomized geometric algorithms. Computers and Euclidean Geometry, 1992.
• 9: Kenneth L. Clarkson , Kasturi Varadarajan, Improved Approximation Algorithms for Geometric Set Cover, Discrete & Computational Geometry, v.37 n.1, p.43-58, January 2007 [doi>10.1007/s00454-006-1273-8]
• 10: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 11: David Haussler and Emo Welzl. ε-nets and simplex range queries. Discrete & Computational Geometry, 2:127--151, 1987.
• 12: János Komlós , János Pach , Gerhard Woeginger, Almost tight bounds for &egr;-nets, Discrete & Computational Geometry, v.7 n.2, p.163-173, 1992 [doi>10.1007/BF02187833]
• 13: Sören Laue. Geometric set cover and hitting sets for polytopes in R³. In Susanne Albers and Pascal Weil, editors, 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), Dagstuhl, Germany, 2008. Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany.
• 14: Jiří Matoušek, Reporting points in halfspaces, Computational Geometry: Theory and Applications, v.2 n.3, p.169-186, Nov. 1992 [doi>10.1016/0925-7721(92)90006-E]
• 15: Jirí Matousek. Epsilon-nets and computational geometry. New Trends in Discrete and Computational Geometry, Algorithms and Combinatorics, 10:69--89, 1993.
• 16: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 17: Jiří Matoušek , Raimund Seidel , E. Welzl, How to net a lot with little: small &egr;-nets for disks and halfspaces, Proceedings of the sixth annual symposium on Computational geometry, p.16-22, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98530]
• 18: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 19: Ketan Mulmuley. Computational Geometry: An Introduction through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
• 20: János Pach , Gerhard Woeginger, Some new bounds for Epsilon-nets, Proceedings of the sixth annual symposium on Computational geometry, p.10-15, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98529]
• 21: Shakhar Smorodinsky, On the chromatic number of some geometric hypergraphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.316-323, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109593]
• 22: V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies to their probabilities. Theory Probab. Appl., 16(2):264--280, 1971.

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:
discrete geometry, hitting sets, hypergraph transversals, strong μ-nets