Geometric set cover problem

The geometric set cover problem is the special case of the set cover problem in geometric settings.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.…

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.

Approximation 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} \le 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.

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

See also

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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1042162217 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001042162217 · captured 1630670704.0 · version history

Cite this page as: encyclopegia.org, “Geometric set cover problem”, snapshot enwiki-001042162217. https://encyclopegia.org/a/geometric-set-cover-problem

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.