Concrete Minkowski sum of polytope and BallInf

[schillic]

Currently we require Polyhedra and CDDLib for the following code:

julia> P = rand(Ball1)
julia> B = rand(BallInf)
julia> minkowski_sum(P, B)

The first time I run this in a fresh session this takes forever (as of writing it still did not terminate) for me.

I have the feeling that there is a better algorithm for this special case, but I am not 100% sure:

• moving/translating P according to B's center (P1 = P + B.center)
• adding the constraints of box_approximation(P) (P2 = box_approximation(P1))
• pushing the constraints outside by B's radius (P3 = push_outside(P2, B.radius) with suitable definition)
• removing redundant constraints (P4 = remove_redundant_constraints!(P3))

[mforets]

a better algorithm for this special case,

for general dimension or in 2d?

julia> using LazySets

julia> P = rand(Ball1); B = rand(BallInf);

# compilation
julia> @time S = convert(HPolygon, minkowski_sum(convert(VPolygon, P), convert(VPolygon, B)));
  1.274598 seconds (3.03 M allocations: 154.306 MiB, 2.25% gc time)

julia> @time S = convert(HPolygon, minkowski_sum(convert(VPolygon, P), convert(VPolygon, B)));
  0.000028 seconds (146 allocations: 12.797 KiB)

EDIT: here are some related issues:

• https://github.com/JuliaReach/LazySets.jl/issues/1597
• https://github.com/JuliaReach/LazySets.jl/issues/1630
• https://github.com/JuliaReach/LazySets.jl/issues/1599

[schillic]

for general dimension or in 2d?

Good point.

1. I think we should do this kind of conversion automatically in 2D, which is for me the most common dimension when I want to play around with an example. It is very nice that it does not require loading external packages and is even (a lot!) faster.

   417.710 μs (1449 allocations: 100.83 KiB)   # minkowski_sum
   9.698 μs (143 allocations: 12.75 KiB)  # your conversion

2. I suggest to keep this issue for the n-dimensional case with a BallInf and implement your conversion (for any two polygons) in a new issue.