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