Encyclopedia

Geometric set cover problem

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated September 3, 2021

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

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.

01Approximation algorithms

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

02Near-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 {polylog} (n))$ time. For example, their algorithms computes an $O(\log \log {\mathsf {OPT}})$ -approximate hitting set in $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)$ -approximate set cover in $O(n\log ^{4}n)$ time for range spaces induced by 2D disks.

Watch videos about Geometric set cover problemExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Geometric set cover problem”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Geometric set cover problem

01Approximation algorithms

02Near-linear-time algorithms

Sources and credits

Related topics

Set cover problem

Vertex cover

Lebesgue covering dimension