セット A と B という 2 つのポイント セットがあり、セット A の各ポイント a について、B のサブセット sub_B を取得しようとします。sub_B の b と a の間の距離は、b と他の任意のポイントの間の距離よりも小さくなります。 Aのポイント。そしてポイントは二次元。たとえば、A = { (0,0), (3,0) }, B = { (1,1), (2,1) } の場合、A の (0,0) のセットは {( 1,1)}、A の (3,0) の場合、そのセットは {(2,1)} です。明らかに、力ずくの方法で O(mn) の結果が得られる可能性があります。ここで、m は A のサイズ、n は B のサイズです。私の質問は、より良い解決策があるかどうかです。
質問する
86 次
1 に答える
1
セット A のすべてのポイントを空間分割ツリーに配置し、 B のすべてのポイントをクエリとして使用して、セット A の最近傍を見つけ、最小距離のポイントのすべてのセットを取得できます。これにより、kd-trees を使用して O(N*log(N)+M*log(N)) ソリューションが得られます。
于 2013-11-15T03:20:52.697 に答える