Small-size ε-nets for axis-parallel rectangles and boxes

ABSTRACT

We show the existence of ε-nets of size O(1/ε log log 1/ε) for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane with "fat" triangular ranges, and for point sets in reals³ and axis-parallel boxes; these are the first known non-trivial bounds for these range spaces. Our technique also yields improved bounds on the size of ε-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of ε-nets of size

O(1/ε log log log 1/ε) for the dual range space of "fat" regions and planar point sets (where the regions are the ground objects and the ranges are subsets stabbed by points). Plugging our bounds into the technique of Bronnimann and Goodrich, we obtain improved approximation factors (computable in randomized polynomial time) for the hitting set or the set cover problems associated with the corresponding range spaces.

REFERENCES

• 1: Pankaj K. Agarwal , Jirí Matousek , Otfried Schwarzkopf, Computing Many Faces in Arrangements of Lines and Segments, SIAM Journal on Computing, v.27 n.2, p.491-505, April 1998 [doi>10.1137/S009753979426616X]
• 2: M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
• 3: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 4: J.D. Boissonnat, M. Sharir, B. Tagansky and M. Yvinec,Voronoi diagrams in higher dimensions under certain polyhedraldistance functions,phDiscrete Comput. Geom., 19:485--519, 1998.
• 5: H. Brönnimann and M. T. Goodrich, Almost optimal set covers in finite VC dimensions, Discrete Comput. Geom., 14:463--479, 1995.
• 6: H. Brönnimann and J. Lenchner,Fast almost-linear-sized nets for boxes in the plane.In Proc. 14th Annu. Fall Workshop Comput. Geom., pp. 36--38, 2004.
• 7: B. Chazelle and J. Friedman,A deterministic view of random sampling and its use in geometry, Combinatorica, 10:229--249, 1990.
• 8: K. L. Clarkson, New applications of random sampling in computational geometry, Discrete Comput. Geom., 2:195--222, 1987.
• 9: Kenneth L. Clarkson, Algorithms for Polytope Covering and Approximation, Proceedings of the Third Workshop on Algorithms and Data Structures, p.246-252, August 11-13, 1993
• 10: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 11: 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]
• 12: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 13: Mark de Berg, Improved Bounds on the Union Complexity of Fat Objects, Discrete & Computational Geometry, v.40 n.1, p.127-140, August 2008 [doi>10.1007/s00454-007-9029-7]
• 14: Mark de Berg , Otfried Cheong , Marc van Kreveld , Mark Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA, 2008
• 15: Alon Efrat, The Complexity of the Union of $(\alpha,\beta)$-Covered Objects, SIAM Journal on Computing, v.34 n.4, p.775-787, 2005 [doi>10.1137/S0097539702407515]
• 16: H. Edelsbrunner , L. Guibas , J. Hershiberger , J. Pach , R. Pollack , R. Seidel , M. Sharir , J. Snoeyink, On arrangements of Jordan arcs with three intersections per pair, Discrete & Computational Geometry, v.4 n.5, p.523-539, 1989 [doi>10.1007/BF02187745]
• 17: Alon Efrat , Matthew J. Katz, On the union of k-curved objects, Computational Geometry: Theory and Applications, v.14 n.4, p.241-254, Dec.1.1999 [doi>10.1016/S0925-7721(99)00036-X]
• 18: A. Efrat and M. Sharir,The complexity of the union of fat objects in the plane, Discrete Comput. Geom. 23:171--189, 2000.
• 19: Tomás Feder , Daniel Greene, Optimal algorithms for approximate clustering, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.434-444, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62255]
• 20: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 21: R. Fowler, M. Paterson, and S. Tanimoto, Optimal packing and covering in the plane are NP-complete, Inform. Process. Lett., 12(3):133--137, 1981.
• 22: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 23: S. Har-Peled, H. Kaplan, M. Sharir, and S. Smorodinsky, ε-nets for halfspaces revisited, manuscript, 2008.
• 24: D. Haussler and E. Welzl,ε-nets and simplex range queries, Discrete Comput. Geom., 2:127--151, 1987.
• 25: Haim Kaplan , Natan Rubin , Micha Sharir , Elad Verbin, Efficient Colored Orthogonal Range Counting, SIAM Journal on Computing, v.38 n.3, p.982-1011, June 2008 [doi>10.1137/070684483]
• 26: R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller, J. W. Thatcher, Eds., Complexity of Computer Computations, pages 85--103, Plenum Press, New York, 1972.
• 27: 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]
• 28: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 29: 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]
• 30: Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Journal of Computer and System Sciences, v.50 n.2, p.203-208, April 1995
• 31: 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]
• 32: Jiri Matousek , Janos Pach , Micha Sharir , Shmuel Sifrony , Emo Welzl, Fat Triangles Determine Linearly Many Holes, SIAM Journal on Computing, v.23 n.1, p.154-169, Feb. 1994 [doi>10.1137/S009753979018330X]
• 33: A. Naamad, D. T. Lee, and W. L. Hsu,On the maximal empty rectangle problem, Discrete Applied Math., 8:267--277, 1984.
• 34: J. Pach and P. K. Agarwal, Combinatorial Geometry, Wiley Interscience, New York, 1995.
• 35: János Pach , Gábor Tardos, On the Boundary Complexity of the Union of Fat Triangles, SIAM Journal on Computing, v.31 n.6, p.1745-1760, 2002 [doi>10.1137/S0097539700382169]
• 36: Evangelia Pyrga , Saurabh Ray, New existence proofs ε-nets, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA [doi>10.1145/1377676.1377708]
• 37: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 38: Kasturi Varadarajan, Epsilon nets and union complexity, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark [doi>10.1145/1542362.1542366]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional 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:
ε-nets, geometric range spaces, hitting set, randomized algorithms, set cover