Near-linear approximation algorithms for geometric hitting sets

ABSTRACT

Given a set system (X,R), the hitting set problem is to find a smallest-cardinality subset H ⊆ X, with the property that each range R ∈ R has a non-empty intersection with H. We present near-linear time approximation algorithms for the hitting set problem, under the following geometric settings: (i) R is a set of planar regions with small union complexity. (ii) R is a set of axis-parallel d-rectangles in d-space. In both cases X is either the entire d-dimensional space or a finite set of points in d-space. The approximation factors yielded by the algorithm are small; they are either the same as or within an O(log n) factor of the best factors known to be computable in polynomial time.

REFERENCES

• 1: P. K. Agarwal. Range searching. In Handbook of Discrete and Computational Geometry, (J. Goodman and J. O'Rourke, eds.), CRC Press, New York, pp. 809--838, 2004.
• 2: Pankaj K. Agarwal , Danny Z. Chen , Shashidhara K. Ganjugunte , Ewa Misiołek , Micha Sharir , Kai Tang, Stabbing Convex Polygons with a Segment or a Polygon, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_5]
• 3: Pankaj K. Agarwal , Mark de Berg , Jirí Matousek , Otfried Schwarzkopf, Constructing Levels in Arrangements and Higher Order Voronoi Diagrams, SIAM Journal on Computing, v.27 n.3, p.654-667, June 1998 [doi>10.1137/S0097539795281840]
• 4: Pankaj K. Agarwal , Alon Efrat , Micha Sharir, Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications, SIAM Journal on Computing, v.29 n.3, p.912-953, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539795295936]
• 5: P. K. Agarwal, E. Ezra, and S. Ganjugunte. Efficient sensor placement for surveillance problems. Submitted for publicaiton.
• 6: 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]
• 7: P. K. Agarwal, J. Pach and M. Sharir. State of the union, of geometric objects: A review.In Surveys on Discrete and Computational Geometry,(J. Goodman, J. Pach and R. Pollack, eds.),AMS, Providence, RI, pp. 9--48, 2008.
• 8: P. K. Agarwal and M. Sharir. Arrangements and their applications. In Handbook of Computational Geometry, (J. Sack and J. Urrutia, eds.), Elsevier, Amsterdam,pp. 49--119, 2000.
• 9: Pankaj K. Agarwal , Junyi Xie , Jun Yang , Hai Yu, Scalable continuous query processing by tracking hotspots, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 10: 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]
• 11: Boris Aronov , Sariel Har-Peled, On Approximating the Depth and Related Problems, SIAM Journal on Computing, v.38 n.3, p.899-921, June 2008 [doi>10.1137/060669474]
• 12: H. Brönnimann and M. T. Goodrich.Almost optimal set covers in finite VC dimensions. Discrete Comput. Geom., 14(1995):463--479.
• 13: Timothy M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, Journal of Algorithms, v.46 n.2, p.178-189, February 2003 [doi>10.1016/S0196-6774(02)00294-8]
• 14: 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]
• 15: 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
• 16: 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]
• 17: 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]
• 18: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 19: 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]
• 20: M. de Berg, K. Dobrindt, and O. Schwarzkopf. On lazy randomized incremental construction. Discrete Comput. Geom., 14(1995):261--286.
• 21: Mark de Berg , Otfried Cheong , Marc van Kreveld , Mark Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA, 2008
• 22: 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]
• 23: 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]
• 24: 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]
• 25: 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]
• 26: R. Fowler, M. Paterson, and S. Tanimoto. Optimal packing and covering in the plane are NP-complete. Inf. Proc. Letts, 12(1981):133--137.
• 27: G. N. Frederickson and D. B. Johnson. Generalized selectionand ranking: sorted matrices. SIAM J. Comput.,13(1984):14--30.
• 28: 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
• 29: D. Haussler and E. Welzl. ε-nets and simplex range queries.phDiscrete Comput. Geom., 2(1987):127--151.
• 30: Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985 [doi>10.1145/2455.214106]
• 31: S. Lauen. Geometric set cover and hitting sets for polytopes in R³. Proc. 25th Int. Sympos. Theoret. Aspects Comput. Sci., 479--490, 2008.
• 32: 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]
• 33: 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]
• 34: 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]
• 35: 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]
• 36: 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]
• 37: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 38: K. Mulmuley. Computational Geometry: An Introduction through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
• 39: 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]
• 40: 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]
• 41: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 42: J. Urrutia. Art Gallery and illumination problems. In Handbook of Computational Geometry, (J. Sack and J. Urrutia, eds), Elsevier, Amsterdam, pages 973--1027, 2000.
• 43: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001

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:
geometric range spaces, hitting sets, randomized algorithms, shallow cuttings, union of simply-shaped regions