単位円板に収まるポイントセットの最大サブセット
セットがあるとしましょう $P$ の $n$ 平面上の点、そして $P_1, \dots, P_k$ の別個のサブセットである $P$ すべてのポイントが $P_i$ すべての1つのユニットディスク内に収まります $i$、 $1\le i\le k$。
また、それぞれ $P_i$ は最大です。つまり、次のサブセットをカバーできる単位円板はありません。 $P$ それはの厳密なスーパーセットです $P_i$。視覚的に言えば、カバーする単位円板を動かすと$P_i$ にないポイントをカバーする $P_i$、その後、そのディスク内にあった少なくとも1つのポイントがカバーされなくなります。
次に例を示します。
上の図では、3つの最大サブセットがあります。
この問題に名前があるのか、以前に研究されたのかはわかりませんが、ここに私の質問があります。
- できる $k$ に関して指数関数的であること $n$？
- そうでない場合は、多項式時間wrtでこれらの最大サブセットを見つけることができますか $n$？
次の議論のために、そのようなサブセットは指数関数的に多いと思います。
点が半径を持ついくつかのディスクの中心であると仮定します。$1/2$。そのような点のサブセットが単位円板に収まる場合、それらはクリークを形成します。ディスクのセットには指数関数的に多くのクリークがあるため、単位円板に収まるこの特定のポイントのセットの最大のサブセットが指数関数的に多くなるはずです。
回答
関数を定義しましょう $f: \Bbb R \times \Bbb R \rightarrow \left [0, n \right ] $、セットからいくつかのポイントを返します $P$、ポイントを中心とした単位円板で覆われています $(x, y)$。これは区分的に一定の関数であり、その定義域は、セットの点を中心とする単位円板のすべての交点によって定義される平面の細分割と見なすことができます。$P$。このサブディビジョンには、頂点（=交点）、エッジ（=円弧）、および面（=平面の一部であり、関数$f$同じ値を返します）。これらの面にはこの値のラベルが付いていると言えます。
この細分化によって定義された平面グラフは4規則グラフであると想定します。これは一般的な想定であり、 $P$一般的な位置にあります（各交点は正確に2つの円に属します）。そのような細分化の例$n=3$ は下にあり、各面（外部面を含む）のラベルは赤色で示されています。
私があなたの最大のサブセットを理解している限り $P_i$隣接する面のすべてのラベルよりも大きいラベルを持つ、このサブディビジョンのそのような面に関連付けることができます。これは、最大サブセットの定義で使用した「移動ディスク」セマンティクスの一種の静的な解釈です。
すべての単位円がペアで交差する場合、サブディビジョンにはできるだけ多くの面が含まれます。この場合、次のことを示すことができます。
- 頂点の数は $n(n-1)$
- エッジの数は $2n(n-1)$
- 面の数は $n(n-1)+2$
したがって、あなたの質問に対する答えは次のようになります。
- いいえ、番号 $k$ 最大サブセットの数は $O(n^2)$、すべての面の数を超えることはできないためです。
- はい、すべての最大サブセットはで見つけることができます $O(n^3)$ ナイーブスキャンアルゴリズムによる時間。
名前、この問題の-それはユニットディスクカバーの問題のいくつかのバリエーションに関連することができるように見えます。