# Minkowski sum in julia

**URL:** <https://discourse.julialang.org/t/minkowski-sum-in-julia/7004>\
**Category:** Numerics\
**Tags:** question, package, linearalgebra\
**Created:** [November 11, 2017, 2:50am UTC](https://discourse.julialang.org/t/minkowski-sum-in-julia/7004 "2017-11-11T02:50:19Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![Sharabh\_Shukla](https://avatars.discourse-cdn.com/v4/letter/s/4af34b/32.png) [@Sharabh\_Shukla](https://discourse.julialang.org/u/Sharabh_Shukla)\
**Post date:** [November 11, 2017, 2:50am UTC](https://discourse.julialang.org/t/minkowski-sum-in-julia/7004/1 "2017-11-11T02:50:19Z")

</div>

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??

---

<div class="post-metadata">

**Author:** ![mforets](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mforets/32/298_2.png) [@mforets](https://discourse.julialang.org/u/mforets)\
**Post date:** [April 17, 2020, 12:52pm UTC](https://discourse.julialang.org/t/minkowski-sum-in-julia/7004/2 "2020-04-17T12:52:12Z")

</div>

To answer this (old) question: this is best done by storing the Minkowski sum _lazily_, then approximating it using [support functions](https://en.wikipedia.org/wiki/Support_function):

```julia
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)

```

 ![Screenshot from 2020-04-17 09-45-38](https://global.discourse-cdn.com/julialang/original/3X/8/2/821b10de207ae326b8002e5731d395e8176988e3.png)

Some benchmark results:

```julia
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.)