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 [math]\displaystyle{ \Sigma = (X, \mathcal{R}) }[/math] where [math]\displaystyle{ X }[/math] is a universe of points in [math]\displaystyle{ \mathbb{R}^d }[/math] and [math]\displaystyle{ \mathcal{R} }[/math] is a family of subsets of [math]\displaystyle{ X }[/math] called ranges, defined by the intersection of [math]\displaystyle{ X }[/math] and geometric shapes such as disks and axis-parallel rectangles. The goal is to select a minimum-size subset [math]\displaystyle{ \mathcal{C} \subseteq \mathcal{R} }[/math] of ranges such that every point in the universe [math]\displaystyle{ X }[/math] is covered by some range in [math]\displaystyle{ \mathcal{C} }[/math]. Given the same range space [math]\displaystyle{ \Sigma }[/math], a closely related problem is the geometric hitting set problem, where the goal is to select a minimum-size subset [math]\displaystyle{ H \subseteq X }[/math] of points such that every range of [math]\displaystyle{ \mathcal{R} }[/math] has nonempty intersection with [math]\displaystyle{ H }[/math], i.e., is hit by [math]\displaystyle{ H }[/math].

In the one-dimensional case, where [math]\displaystyle{ X }[/math] contains points on the real line and [math]\displaystyle{ \mathcal{R} }[/math] 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 [math]\displaystyle{ \mathcal{R} }[/math] 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 [math]\displaystyle{ O(\log n) }[/math] approximation, where [math]\displaystyle{ n = \max\{|X|, |\mathcal{R}|\} }[/math]. 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 [math]\displaystyle{ O(\log \mathsf{OPT}) }[/math]-approximate set cover/hitting set for a range space [math]\displaystyle{ \Sigma }[/math] with constant VC-dimension can be computed in polynomial time, where [math]\displaystyle{ \mathsf{OPT} \le n }[/math] denotes the size of the optimal solution. The approximation ratio can be further improved to [math]\displaystyle{ O(\log \log \mathsf{OPT}) }[/math] or [math]\displaystyle{ O(1) }[/math] when [math]\displaystyle{ \mathcal{R} }[/math] is induced by axis-parallel rectangles or disks in [math]\displaystyle{ \mathbb{R}^2 }[/math], 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 [math]\displaystyle{ O(n~\mathrm{polylog}(n)) }[/math] time. For example, their algorithms computes an [math]\displaystyle{ O(\log \log \mathsf{OPT}) }[/math]-approximate hitting set in [math]\displaystyle{ O(n \log^3n\log\log\log \mathsf{OPT}) }[/math] time for range spaces induced by 2D axis-parallel rectangles; and it computes an [math]\displaystyle{ O(1) }[/math]-approximate set cover in [math]\displaystyle{ O(n \log^4n) }[/math] time for range spaces induced by 2D disks.

See also

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