Epsilon nets and union complexity

ABSTRACT

We consider the following combinatorial problem: given a set of n objects (for example, disks in the plane, triangles), and an integer L ≥ 1, what is the size of the smallest subset of these n objects that covers all points that are in at least L of the objects? This is the classic question about the size of an L/n-net for these objects. It is well known that for fairly general classes of geometric objects the size of an L/n-net is O(n/L log n/L). There are some instances where this general bound can be improved, and this improvement is usually due to bounds on the combinatorial complexity (size) of the boundary of the union of these objects. Thus, the boundary of the union of m disks has size O(m), and this translates to an O(n/L) bound on the size of an L/n-net for disks. For m fat triangles, the size of the union boundary is O(m log log m), and this yields L/n-nets of size O(n/L log log n/L). Improved nets directly translate into an upper bound on the ratio between the optimal integral solution and the optimal fractional solution for the corresponding geometric set cover problem. Thus, for covering k points by disks, this ratio is O(1); and for covering k points by fat triangles, this ratio is O(log log k). This connection to approximation algorithms for geometric set cover is a major motivation for attempting to improve bounds on nets. Our main result is an argument that in some cases yields nets that are smaller than those previously obtained from the size of the union boundary. Thus for fat triangles, for instance, we obtain nets of size O(n/L log log log n). We use this to obtain a randomized polynomial time algorithm that gives an O(log log log k)-approximation for the problem of covering k points by the smallest subset of a given set of triangles.

REFERENCES

• 1: Noga Alon , Shakhar Smorodinsky, Conflict-free colorings of shallow discs, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137864]
• 2: N. Alon and J. H. Spencer. The Probabilistic Method.John Wiley and Sons, Inc. 1992.
• 3: Boris Aronov , Esther Ezra , Micha Shair, Small-size ε-nets for axis-parallel rectangles and boxes, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA [doi>10.1145/1536414.1536501]
• 4: Boaz Ben-Moshe , Matthew J. Katz , Joseph S. B. Mitchell, A constant-factor approximation algorithm for optimal terrain guarding, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 5: H. Brönnimann and M. T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom., 14:263--279, 1995.
• 6: Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Journal of Algorithms, v.21 n.3, p.579-597, Nov. 1996 [doi>10.1006/jagm.1996.0060]
• 7: V. Chvátal. A greedy heuristic for the set-covering problem. Math. Oper. Res., 4:233--235, 1979.
• 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: Guy Even , Dror Rawitz , Shimon Shahar, Hitting sets when the VC-dimension is small, Information Processing Letters, v.95 n.2, p.358-362, 31 July 2005 [doi>10.1016/j.ipl.2005.03.010]
• 13: 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]
• 14: D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Discrete Comput. Geom., 2:127--151, 1987.
• 15: D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci., 9:256--278, 1974.
• 16: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• 17: V. S. Anil Kumar , H. Ramesh, Covering Rectilinear Polygons with Axis-Parallel Rectangles, SIAM Journal on Computing, v.32 n.6, p.1509-1541, 2003 [doi>10.1137/S0097539799358835]
• 18: L. Lovász. On the ratio of optimal integral and fractional covers. Discrete Math., 13:383--390, 1975.
• 19: 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]
• 20: 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]
• 21: 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]
• 22: K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1993.
• 23: 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]
• 24: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996

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:
approximation algorithms, epsilon nets, set cover