# Minkowski sum in julia

I have new hundred polytopes in H representation. I would like to find the Minkowski sum of all these polytopes, I am aware that the problem is difficult I was looking for an approximate algorithm in julia that can do the job for me efficiently. Anybody aware of such a function in julia??

To answer this (old) question: this is best done by storing the Minkowski sum lazily, then approximating it using support functions:

``````using LazySets, Plots

X = MinkowskiSumArray([rand(HPolygon) for _ in 1:10]);
Y = overapproximate(X, PolarDirections(20));

plot([Xi for Xi in array(X)], ratio=1.)
plot!(Y, alpha=.2, lab="approximate")
plot!(X, 1e-6, alpha=.2, lab="true") # (uses iterative refinement with given tolerance)
``````

Some benchmark results:

``````using BenchmarkTools

# Experiment 1:
# A hundred random polygons (dimension 2)
aux = [rand(HPolygon) for _ in 1:100]
dirs = PolarDirections(20) # overapproximate with uniformly distributed directions over S1
@btime overapproximate(MinkowskiSumArray(\$aux), \$dirs);
1.128 ms (24164 allocations: 1.34 MiB)

# Experiment 2:
# A hundred random polytopes in dimension ten
aux = [HPolytope(constraints_list(rand(10, 10) * rand(Hyperrectangle, dim=10))) for _ in 1:100];
dirs = OctDirections(10)  # overapproximate with octagonal directions
@btime overapproximate(MinkowskiSumArray(\$aux), \$dirs);
1.985 s (1742135 allocations: 327.33 MiB)
``````

(If the data is given as static arrays then the computations are faster.)

2 Likes