0

2 次元の点の大きなセットと、2 つの距離 、dおよび がありDます。

次のようなポイントのサブセットを見つける必要があります。

  • dサブセットの各メンバーは、サブセットの他のすべてのメンバーからの距離よりも小さいです。

  • Dサブセットの各メンバーは、サブセットのメンバーではないすべてのポイントからの距離以上です。

ご覧のとおり、これらのサブセットは複数ある場合もあれば、1 つある場合もあれば、まったくない場合もあります。

アイデアはたくさんありましたが、1 つのアイデアを最後まで実行することはできませんでした。

説明:

ポイントの数は数百になる可能性があります。距離は整数 - 1,2,3 ... n

私の主なアイデアは次のとおりです。

4点しか持っていないとしましょう。

  • 最初に、すべての点のペアを保持し、それらの間の距離が d よりも小さいか、D よりも大きいか、またはまったくない場合に true/false を示す構造を作成することを考えました。すなわち:

     point1     point2       <d     >D
   a          b         true    false
   a          c         false   true
   a          d         false   false
   b          c         false   false
   b          d         true    false

このデータを使用して、両方の false を持つ行を持つ各ポイントは、クラスターに含まれないことを意味することがわかりました。

ここで、クラスターに使用できるポイントを残したので、それらのチェックを開始します。

これは私が止めた部分です...

4

0 に答える 0