[PPL-devel] Minkowski-Sum

[Roberto Bagnara]

On 07/16/14 14:21, Stefan Schupp wrote:
> I am currently searching for a possibility to obtain the Minkowski-Sum of two polyhedra. My first idea was to unify the sets of generators from both polyhedra, as from the documentation I can take that a single polytope is generated by the Minkowski-Sum of its generators. Would you suggest this approach or is there a better way to go?

Hi Stefan,

adding an implementation of Minkowski addition has been on
our todo list for quite some time.  It was never implemented
for lack of interest and manpower.  Last time I looked at this,
the algorithm described in

    K. Fukuda.
    From the zonotope construction to the Minkowski addition
    of convex polytopes.
    J. Symbolic Comput., 38(4):1261-1272, 2004.

seemed a good candidate.
Kind regards,

   Roberto

-- 
     Prof. Roberto Bagnara

Applied Formal Methods Laboratory - University of Parma, Italy
mailto:bagnara at cs.unipr.it
                              BUGSENG srl - http://bugseng.com
                              mailto:roberto.bagnara at bugseng.com