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?

java algorithm set

Edit Report

1 Answer

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.

answered 2012-07-13T18:27:58.607

Efficient Minkowski sum calculation

1 Answer

Your Answer