search

JuliaReach / LazySets.jl

Scalable symbolic-numeric set computations in Julia
https://juliareach.github.io/LazySets.jl/
Other
226 stars 32 forks source link

Faster vertex enumeration for zonotopes #1404

Open schillic opened 5 years ago

schillic commented 5 years ago

The algorithm in [1] (which uses [2]) enumerates all vertices of a zonotope using linear programming. This is more efficient than enumerating all 2^n combinations of {-1, 1} factors for each generator that we have implemented because many of these vertices are redundant.

[1] http://dx.doi.org/10.1016/j.ejor.2003.04.011 [2] http://dx.doi.org/10.1016/0166-218X(95)00026-N

schillic commented 4 years ago

Another paper that proposes several algorithms to solve this problem: https://arxiv.org/abs/1912.02439