Geometric set cover problem

The geometric set cover problem is the special case of the set cover problem in geometric settings. The input is a range space Σ=(X,ℛ) where X is a universe of points in ℝd and ℛ is a family of subsets of X called ranges, defined by the intersection of X and geometric shapes such as disks and axis-parallel rectangles. The goal is to select a minimum-size subset 𝒞⊆ℛ of ranges such that every point in the universe X is covered by some range in 𝒞.

Given the same range space Σ, a closely related problem is the geometric hitting set problem, where the goal is to select a minimum-size subset H⊆X of points such that every range of ℛ has nonempty intersection with H, i.e., is hit by H.

In the one-dimensional case, where X contains points on the real line and ℛ is defined by intervals, both the geometric set cover and hitting set problems can be solved in polynomial time using a simple greedy algorithm. However, in higher dimensions, they are known to be NP-complete even for simple shapes, i.e., when ℛ is induced by unit disks or unit squares. The discrete unit disc cover problem is a geometric version of the general set cover problem which is NP-hard.

Many approximation algorithms have been devised for these problems. Due to the geometric nature, the approximation ratios for these problems can be much better than the general set cover/hitting set problems. Moreover, these approximate solutions can even be computed in near-linear time.

Approximation algorithms

The greedy algorithm for the general set cover problem gives O(log⁡n) approximation, where n=max⁡{|X|,|ℛ|}. This approximation is known to be tight up to constant factor. However, in geometric settings, better approximations can be obtained. Using a multiplicative weight algorithm, Brönnimann and Goodrich showed that an O(log⁡𝖮𝖯𝖳)-approximate set cover/hitting set for a range space Σ with constant VC-dimension can be computed in polynomial time, where 𝖮𝖯𝖳≤n denotes the size of the optimal solution. The approximation ratio can be further improved to O(log⁡log⁡𝖮𝖯𝖳) or O(1) when ℛ is induced by axis-parallel rectangles or disks in ℝ2, respectively.

Near-linear-time algorithms

Based on the iterative-reweighting technique of Clarkson and Brönnimann and Goodrich, Agarwal and Pan gave algorithms that computes an approximate set cover/hitting set of a geometric range space in O(n polylog(n)) time. For example, their algorithms computes an O(log⁡log⁡𝖮𝖯𝖳)-approximate hitting set in O(nlog3nlog⁡log⁡log⁡𝖮𝖯𝖳) time for range spaces induced by 2D axis-parallel rectangles; and it computes an O(1)-approximate set cover in O(nlog4n) time for range spaces induced by 2D disks.

See also

References

  1. ↑ Fowler, R.J.; Paterson, M.S.; Tanimoto, S.L. (1981), "Optimal packing and covering in the plane are NP-complete", Inf. Process. Lett., 12 (3): 133–137, doi:10.1016/0020-0190(81)90111-3
  2. ↑ https://cs.uwaterloo.ca/~alopez-o/files/OtDUDCP_2011.pdf On the Discrete Unit Disk Cover Problem
  3. 1 2 Agarwal, Pankaj K.; Pan, Jiangwei (2014). "Near-Linear Algorithms for Geometric Hitting Sets and Set Covers". Proceedings of the thirtieth annual symposium on Computational Geometry.
  4. ↑ Feige, Uriel (1998), "A threshold of ln n for approximating set cover", Journal of the ACM, 45 (4): 634–652, CiteSeerX 10.1.1.70.5014, doi:10.1145/285055.285059, S2CID 52827488 {{citation}}: Cite uses deprecated parameter |citeseerx= (help)
  5. ↑ Arora, S.; Hazan, E.; Kale, S. (2012), "The Multiplicative Weights Update Method: a Meta-Algorithm and Applications", Theory of Computing, 8: 121–164, doi:10.4086/toc.2012.v008a006
  6. 1 2 Brönnimann, H.; Goodrich, M. (1995), "Almost optimal set covers in finite VC-dimension", Discrete & Computational Geometry, 14 (4): 463–479, doi:10.1007/bf02570718
  7. ↑ Clarkson, Kenneth L. (1993-08-11). "Algorithms for polytope covering and approximation". In Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; et al. (eds.). Algorithms and Data Structures. Lecture Notes in Computer Science. Vol. 709. Springer Berlin Heidelberg. pp. 246–252. doi:10.1007/3-540-57155-8_252. ISBN 978-3-540-57155-1.