Geometric set cover problem explained

The geometric set cover problem is the special case of the set cover problem in geometric settings. The input is a range space

\Sigma = (X, l{R}) where X is a universe of points in R ^{d} and l{R} 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 l{C} \subseteq l{R} of ranges such that every point in the universe X is covered by some range in l{C} .

Given the same range space

\Sigma , a closely related problem is the geometric hitting set problem, where the goal is to select a minimum-size subset H \subseteq X of points such that every range of l{R} 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 l{R} 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 l{R} 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.^[1]

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.^[2]

Approximation algorithms

The greedy algorithm for the general set cover problem gives

O( log n) approximation, where n = max \{|X|, | l{R}|\} . 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 OPT ) -approximate set cover/hitting set for a range space \Sigma with constant VC-dimension can be computed in polynomial time, where OPT \le n denotes the size of the optimal solution. The approximation ratio can be further improved to O( log log OPT ) or O( 1 ) when l{R} is induced by axis-parallel rectangles or disks in R ^{2} , respectively.

Near-linear-time algorithms

Based on the iterative-reweighting technique of Clarkson^[3] 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 OPT ) -approximate hitting set in O(n log ^{3nlogloglog} OPT ) time for range spaces induced by 2D axis-parallel rectangles; and it computes an O( 1 ) -approximate set cover in O(n log ^{4n)} time for range spaces induced by 2D disks.

See also

• Set cover problem
• Vertex cover
• Lebesgue covering dimension
• Carathéodory's extension theorem

Notes and References

1. https://cs.uwaterloo.ca/~alopez-o/files/OtDUDCP_2011.pdf On the Discrete Unit Disk Cover Problem
2. Pankaj K. . Agarwal . Jiangwei . Pan . Near-Linear Algorithms for Geometric Hitting Sets and Set Covers . Proceedings of the thirtieth annual symposium on Computational Geometry . 2014 .
3. Book: Clarkson, Kenneth L.. Springer Berlin Heidelberg. 1993-08-11. 978-3-540-57155-1. 246–252. Lecture Notes in Computer Science. 10.1007/3-540-57155-8_252. Frank. Dehne. Jörg-Rüdiger. Sack. Nicola. Santoro. Sue. 3 . Whitesides. Algorithms and Data Structures. 709. Algorithms for polytope covering and approximation.