On the set multi-cover problem in geometric settings

ABSTRACT

We consider the set multi-cover problem in geometric settings. Given a set of points P and a collection of geometric shapes (or sets) F, we wish to find a minimum cardinality subset of F such that each point p ∈ P is covered by (contained in) at least demands d(p) sets. Here demands d(p) is an integer demand (requirement) for p. When the demands demands d(p)=1 for all p, this is the standard set cover problem. The set cover problem in geometric settings admits an approximation ratio that is better than that for the general version. In this paper, we show that similar improvements can be obtained for the multi-cover problem as well. In particular, we obtain an O(log Opt) approximation for set systems of bounded VC-dimension, and an O(1) approximation for covering points by half-spaces in three dimensions and for some other classes of shapes.

REFERENCES

• 1: 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]
• 2: J. D. Boissonnat, M. Sharir, B. Tagansky, and M. Yvinec. Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete Comput. Geom., 19(4):485--519, 1998.
• 3: H. Brönnimann and M. T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom., 14:263--279, 1995.
• 4: B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. Combinatorica, 10(3):229--249, 1990.
• 5: Chandra Chekuri , Kenneth L. Clarkson , Sariel Har-Peled, On the set multi-cover problem in geometric settings, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark [doi>10.1145/1542362.1542421]
• 6: K. L. Clarkson, Applications of random sampling in computational geometry, II, Proceedings of the fourth annual symposium on Computational geometry, p.1-11, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73394]
• 7: 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
• 8: 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]
• 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: M. de Berg and O. Schwarzkopf. Cuttings and applications. Internat. J. Comput. Geom. Appl., 5:343--355, 1995.
• 11: 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]
• 12: 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]
• 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: Christodoulos Fragoudakis , Euripides Markou , Stathis Zachos, Maximizing the guarded boundary of an Art Gallery is APX-complete, Computational Geometry: Theory and Applications, v.38 n.3, p.170-180, October, 2007 [doi>10.1016/j.comgeo.2006.12.001]
• 15: S. Har-Peled. Geometric approximation algorithms. Class notes. Online at http://uiuc.edu/sariel/teach/notes/aprx/, 2008.
• 16: Yi Li , Philip M. Long , Aravind Srinivasan, Improved bounds on the sample complexity of learning, Journal of Computer and System Sciences, v.62 n.3, p.516-527, May 2001 [doi>10.1006/jcss.2000.1741]
• 17: Philip M. Long, Using the Pseudo-Dimension to Analyze Approximation Algorithms for Integer Programming, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.26-37, August 08-10, 2001
• 18: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
• 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: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 21: J. Pach and P. K. Agarwal. Combinatorial Geometry. John Wiley & Sons, New York, NY, 1995.
• 22: My T. Thai , Feng Wang , David Hongwei Du , Xiaohua Jia, Coverage problems in wireless sensor networks: designs and analysis, International Journal of Sensor Networks, v.3 n.3, p.191-200, May 2008 [doi>10.1504/IJSNET.2008.018485]
• 23: 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]
• 24: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms

Keywords:
LP rounding, cuttings, set cover