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 , R ) {\displaystyle \Sigma =(X,{\mathcal {R}})} where X {\displaystyle X} is a universe of points in R d {\displaystyle \mathbb {R} ^{d}} and R {\displaystyle {\mathcal {R}}} is a family of subsets of X {\displaystyle X} called ranges, defined by the intersection of X {\displaystyle X} and geometric shapes such as disks and axis-parallel rectangles. The goal is to select a minimum-size subset C ⊆ R {\displaystyle {\mathcal {C}}\subseteq {\mathcal {R}}} of ranges such that every point in the universe X {\displaystyle X} is covered by some range in C {\displaystyle {\mathcal {C}}} .

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

In the one-dimensional case, where X {\displaystyle X} contains points on the real line and R {\displaystyle {\mathcal {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 R {\displaystyle {\mathcal {R}}} 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]

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

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 O ( n   p o l y l o g ( n ) ) {\displaystyle O(n~\mathrm {polylog} (n))} time. For example, their algorithms computes an O ( log ⁡ log ⁡ O P T ) {\displaystyle O(\log \log {\mathsf {OPT}})} -approximate hitting set in O ( n log 3 ⁡ n log ⁡ log ⁡ log ⁡ O P T ) {\displaystyle O(n\log ^{3}n\log \log \log {\mathsf {OPT}})} time for range spaces induced by 2D axis-parallel rectangles; and it computes an O ( 1 ) {\displaystyle O(1)} -approximate set cover in O ( n log 4 ⁡ n ) {\displaystyle O(n\log ^{4}n)} time for range spaces induced by 2D disks.

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