java - 効率的なミンコフスキー和の計算

Question

離散1次元ミンコフスキー和を効率的に計算するアルゴリズムがあるのだろうか。ミンコフスキー和は次のように定義されます。

S + T = { x + y | x in S, y in T }

セットをリストとして表し、SとTを並べ替えてから、2つのセットの和集合を計算するのと同じようなことを行うことができるのでしょうか。つまり、セットに沿って並行して歩き、結果を生成します。

重複するケースx1+y1 = x2 + y2を削除するために結果を追加でソートする必要がない、そのようなアルゴリズムは知られていますか？できればJavaで作成しますか？

score 5 · Accepted Answer

まず、出力のサイズは、衝突がO(nm)ない場合 (たとえばA={0, 1, 2, ..., n-1}、単純なものは、すべてのペア ( ) を計算し、並べ替えと一意化 (合計.B={n, 2*n, 3*n, ...n*n}nmO(nm)O(nm log nm)

all inのMような上限がある場合、次の方法で合計を計算できます。x <= MxA union BO(M log M)

A[i] = 1 ff i \in A, 0 otherwiseについても同様に、特性ベクトルを生成しBます。そのような各ベクトルのサイズはMです。
FFT を使用してAとの畳み込みを計算します (時間: )。出力サイズは O( ) です。BO(M log M)M
スキャン出力-がミンコフスキー和の要素である場合O、各セルでO[i]非ゼロです。i

証明:および、 iffおよび、 iff 、つまりがミンコフスキー和O[i] != 0に存在する場合。kA[k] != 0B[i-k] != 0k \in Ai-k \in Bk + i-ki

（本紙より引用）

score 0 · Accepted Answer

S と T を並べ替え、S を反復処理して T 内の一致する要素を探し、一致が見つかるたびに S と T から要素を削除し、新しいセット U に入れます。これらは並べ替えられているため、T で一致する要素が見つかったらT でのさらなる比較は、最後の一致から開始できます。

これで、S、T、および U はすべて互いに素になります。そのため、S と T を反復処理し、S と U、および T と U をそれぞれ追加します。最後に U を反復処理し、U のすべての要素を、現在のセットインデックス以上のセットインデックスを持つ U のすべての要素ごとに追加します。

悲しいことに、この最適化ではアルゴリズムはまだ O(n^2) です。T と S が同一の場合、単純なソリューションよりも 2 倍高速になります。また、出力セットで重複を検索する必要もありません。

2 に答える 2