CODEWITHSUNDEEP
javaalgorithmset
user502187
user502187

Reputation:

Efficient Minkowski sum calculation

I wonder whether there is an algorithm to efficiently calculate a discrete 1-dimensional Minkowski sum. The Minkowski sum is defined as:

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

Could it be that we can represent the sets as lists, sort S and T, and then do something similarly to computing the union of two sets. i.e. walk along the sets in parallel and generate the result.

Are there such algorithms known where I don't have to additionally sort the result to remove overlapping cases x1+y1 = x2+y2? Preferably formulated in Java?

Upvotes: 8

Views: 4077

Answers (2)

user1071136
user1071136

Reputation: 15725

First, the size of the output can be O(nm), if there are no collisions (e.g., A={0, 1, 2, ..., n-1}, B={n, 2*n, 3*n, ...n*n}), so if we depend on n and m, we have no hope of finding a sub-quadratic algorithm. A straightforward one is computing all pairs (O(nm)), sorting and unique-ing (total of O(nm log nm).

If you have an upper bound M such that x <= M for all x in A union B, we can compute the sum in O(M log M) in the following way.

  1. Generate the characteristic vectors A[i] = 1 ff i \in A, 0 otherwise and similarly for B. Each such vector is of size M.

  2. Compute the convolution of A and B using FFT (time: O(M log M)). Output size is O(M).

  3. Scan output O - at each cell, O[i] is nonzero iff i is an element of the Minkowski sum.

Proof: O[i] != 0 iff there exists k such that A[k] != 0 and B[i-k] != 0, iff k \in A and i-k \in B, iff k + i-k, that is i, is in the Minkowski sum.

(Taken from this paper)

Upvotes: 5

Rafael Baptista
Rafael Baptista

Reputation: 11499

Sort S and T, iterate over S searching for matching elements in T, each time you find a match remove the element from S and T and put it in a new set U. Because they are sorted, once you find a match in T, further comparisons in T can start from the last match.

Now S, T and U are all disjoint. So iterate over S and T adding each one, and S and U, and T and U. Finally iterate over U, and add every element in U by every element in U whose set index is equal to or greater than the current set index.

Sadly the algorithm is still O(n^2) with this optimization. If T and S are identical it will be 2x faster than the naive solution. You also don't have to search in the output set for duplicates.

Upvotes: 0

Related Questions