Jump to content

Geometric set cover problem

From Wikipedia, the free encyclopedia
(Redirected from 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 where is a universe of points in and is a family of subsets of called ranges, defined by the intersection of 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 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 of points such that every range of has nonempty intersection with , i.e., is hit by .

In the one-dimensional case, where 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.[1] The discrete unit disc cover problem is a geometric version of the general set cover problem which is NP-hard.[2]

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.[3]

Approximation algorithms

[edit]

The greedy algorithm for the general set cover problem gives approximation, where . This approximation is known to be tight up to constant factor.[4] However, in geometric settings, better approximations can be obtained. Using a multiplicative weight algorithm,[5] Brönnimann and Goodrich[6] showed that an -approximate set cover/hitting set for a range space with constant VC-dimension can be computed in polynomial time, where denotes the size of the optimal solution. The approximation ratio can be further improved to or when is induced by axis-parallel rectangles or disks in , respectively.

Near-linear-time algorithms

[edit]

Based on the iterative-reweighting technique of Clarkson[7] and Brönnimann and Goodrich,[6] Agarwal and Pan[3] gave algorithms that computes an approximate set cover/hitting set of a geometric range space in time. For example, their algorithms computes an -approximate hitting set in time for range spaces induced by 2D axis-parallel rectangles; and it computes an -approximate set cover in time for range spaces induced by 2D disks.

See also

[edit]

References

[edit]
  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. ^ a b 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
  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. ^ a b 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.