高效的Minkowski总和计算

Question

我想知道是否有一种算法可以有效地计算离散的一维 Minkowski和.Minkowski总和定义为:

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

可能是我们可以将集合表示为列表,对S和T进行排序,然后类似于计算两个集合的并集.即并行地沿着集合行走并生成结果.

是否有已知的算法,我不必另外对结果进行排序以删除重叠的情况x1 + y1 = x2 + y2？最好用Java配制？

Answer 1

首先,输出的大小可以O(nm),如果没有冲突(例如A={0, 1, 2, ..., n-1},B={n, 2*n, 3*n, ...n*n}),所以如果我们依靠n和m,我们没有找到一个子二次算法的希望.一个简单的方法是计算所有对(O(nm)),排序和唯一(总计)O(nm log nm).

如果你有一个上限M,使得x <= M对所有x的A union B,我们可以计算的总和O(M log M)以下列方式.

1. 生成特征向量A[i] = 1 ff i \in A, 0 otherwise,类似于B.每个这样的载体都是大小的M.

2. 计算FFT 的卷积A和B使用FFT(时间:) O(M log M).输出大小为O(M).

3. 扫描输出O- 在每个单元格,O[i]非零iff i是Minkowski和的元素.

证明:O[i] != 0当且仅当存在k这样A[k] != 0和B[i-k] != 0,敌我识别k \in A和i-k \in B,当且仅当k + i-k,那就是i,在闵可夫斯基总和.

(摘自本文)

Answer 2

对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 倍。您也不必在输出集中搜索重复项。