幾何集合被覆問題

幾何集合被覆問題は、幾何学的設定における集合被覆問題の特殊なケースです。入力は範囲空間で、は内の点の集合であり、は範囲と呼ばれるのサブセットの族であり、と円板や軸平行長方形などの幾何図形の交差によって定義されます。目標は、集合内のすべての点が内の何らかの範囲で覆われるような、範囲の最小サイズの部分集合を選択することです。 ${\displaystyle \Sigma =(X,{\mathcal {R}})}$${\displaystyle X}$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle {\mathcal {R}}}$${\displaystyle X}$${\displaystyle X}$${\displaystyle {\mathcal {C}}\subseteq {\mathcal {R}}}$${\displaystyle X}$${\displaystyle {\mathcal {C}}}$

同じ範囲空間 が与えられた場合、密接に関連する問題として、のあらゆる範囲がと空でない交差を持つ、つまりが にヒットするような、点の最小サイズのサブセットを選択することが目標となる、幾何的ヒットセット問題 があります。 ${\displaystyle \Sigma }$${\displaystyle H\subseteq X}$${\displaystyle {\mathcal {R}}}$${\displaystyle H}$${\displaystyle H}$

1 次元の場合、 は実数直線上の点を含み、 は区間によって定義され、幾何学的集合被覆問題とヒッティング集合問題は両方とも、単純な貪欲アルゴリズム を用いて多項式時間で解くことができます。しかし、より高次元では、が単位円または単位正方形によって誘導される場合など、単純な形状であってもNP 完全であることが知られています。 ^[1]離散単位円被覆問題は、NP 困難である一般集合被覆問題の幾何学的バージョンです。^[2]${\displaystyle X}$${\displaystyle {\mathcal {R}}}$${\displaystyle {\mathcal {R}}}$

これらの問題に対しては多くの近似アルゴリズムが考案されている。幾何学的性質のため、これらの問題の近似率は一般的な集合被覆/ヒット集合問題よりもはるかに優れている可能性がある。さらに、これらの近似解はほぼ線形時間で計算することもできる。^[3]

一般的な集合被覆問題に対する貪欲アルゴリズムは、の近似値を与えます。この近似値は、定数因子まで厳密であることが知られています。[ ^{4]しかし、幾何学的な設定では、より良い近似値を得ることができます。}乗法重みアルゴリズムを使用することで、^[5] Brönnimann と Goodrich ^{[6] は}、定数 VC 次元を持つ範囲空間の -近似集合被覆/ヒッティング集合を多項式時間で計算できることを示しました。ここで、 は最適解のサイズを表します。内の軸平行長方形または円板によって がそれぞれ誘導される場合、近似値はまたはにさらに改善できます。 ${\displaystyle O(\log n)}$${\displaystyle n=\max\{|X|,|{\mathcal {R}}|\}}$${\displaystyle O(\log {\mathsf {OPT}})}$${\displaystyle \Sigma }$${\displaystyle {\mathsf {OPT}}\leq n}$${\displaystyle O(\log \log {\mathsf {OPT}})}$${\displaystyle O(1)}$${\displaystyle {\mathcal {R}}}$${\displaystyle \mathbb {R} ^{2}}$

^{Clarkson [7]}と Brönnimann と Goodrich ^[6]の反復再重み付け手法に基づいて、 Agarwal と Pan ^{[3] は}、時間内で幾何学的範囲空間の近似セットカバー/ヒッティングセットを計算するアルゴリズムを提示しました。たとえば、彼らのアルゴリズムは、 2D 軸平行長方形によって誘導される範囲空間の-近似ヒットセットを時間内で計算します。また、2D ディスクによって誘導される範囲空間の-近似セットカバーを時間内で計算します。 ${\displaystyle O(n~\mathrm {polylog} (n))}$${\displaystyle O(\log \log {\mathsf {OPT}})}$${\displaystyle O(n\log^{3}n\log\log\log{\mathsf{OPT}})}$${\displaystyle O(1)}$${\displaystyle O(n\log^{4}n)}$

• セットカバーの問題
• 頂点カバー
• ルベーグ被覆次元
• カラテオドリの拡張定理