Английская Википедия: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>\Sigma = (X, \mathcal{R})</math> where <math>X</math> is a universe of points in <math>\mathbb{R}^d</math> and <math>\mathcal{R}</math> is a family of subsets of <math>X</math> called ranges, defined by the intersection of <math>X</math> and geometric shapes such as disks and axis-parallel rectangles. The goal is to select a minimum-size subset <math>\mathcal{C} \subseteq \mathcal{R}</math> of ranges such that every point in the universe <math>X</math> is covered by some range in <math>\mathcal{C}</math>.
Given the same range space <math>\Sigma</math>, a closely related problem is the geometric hitting set problem, where the goal is to select a minimum-size subset <math>H \subseteq X</math> of points such that every range of <math>\mathcal{R}</math> has nonempty intersection with <math>H</math>, i.e., is hit by <math>H</math>.
In the one-dimensional case, where <math>X</math> contains points on the real line and <math>\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>\mathcal{R}</math> 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]
Approximation algorithms
The greedy algorithm for the general set cover problem gives <math>O(\log n)</math> approximation, where <math>n = \max\{|X|, |\mathcal{R}|\}</math>. 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 <math>O(\log \mathsf{OPT})</math>-approximate set cover/hitting set for a range space <math>\Sigma</math> with constant VC-dimension can be computed in polynomial time, where <math>\mathsf{OPT} \le n</math> denotes the size of the optimal solution. The approximation ratio can be further improved to <math>O(\log \log \mathsf{OPT})</math> or <math>O(1)</math> when <math>\mathcal{R}</math> is induced by axis-parallel rectangles or disks in <math>\mathbb{R}^2</math>, respectively.
Near-linear-time algorithms
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 <math>O(n~\mathrm{polylog}(n))</math> time. For example, their algorithms computes an <math>O(\log \log \mathsf{OPT})</math>-approximate hitting set in <math>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>O(1)</math>-approximate set cover in <math>O(n \log^4n)</math> time for range spaces induced by 2D disks.
See also
References
- ↑ Шаблон:Citation
- ↑ https://cs.uwaterloo.ca/~alopez-o/files/OtDUDCP_2011.pdf On the Discrete Unit Disk Cover Problem
- ↑ 3,0 3,1 Шаблон:Cite conference
- ↑ Шаблон:Citation
- ↑ Шаблон:Citation
- ↑ 6,0 6,1 Шаблон:Citation
- ↑ Шаблон:Cite book
