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 $\mathrm{\Sigma }=(X,{ℛ})$ where $X$ is a universe of points in ${\mathbb{ℝ}}^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 ${𝒞}\subseteq {ℛ}$ of ranges such that every point in the universe $X$ is covered by some range in ${𝒞}$. Given the same range space $\mathrm{\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 ${ℛ}$ 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 \mathsf{O}\mathsf{P}\mathsf{T})$-approximate set cover/hitting set for a range space $\mathrm{\Sigma }$ with constant VC-dimension can be computed in polynomial time, where $\mathsf{O}\mathsf{P}\mathsf{T}\le n$ denotes the size of the optimal solution. The approximation ratio can be further improved to $O(\log \log \mathsf{O}\mathsf{P}\mathsf{T})$ or $O(1)$ when ${ℛ}$ is induced by axis-parallel rectangles or disks in ${\mathbb{ℝ}}^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\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}(n))$ time. For example, their algorithms computes an $O(\log \log \mathsf{O}\mathsf{P}\mathsf{T})$-approximate hitting set in $O(n{\log }^{3}n\log \log \log \mathsf{O}\mathsf{P}\mathsf{T})$ time for range spaces induced by 2D axis-parallel rectangles; and it computes an $O(1)$-approximate set cover in $O(n{\log }^{4}n)$ time for range spaces induced by 2D disks.

See also

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