Implement Minkowski decomposition of polytopes

[c3a3c5d3-9fc2-4586-b552-eeb8a7e82c23]

I plan to add code for Minkowski Decomposition of Polytopes based on the algorithm in "On the space of Minkowski summands of a convex polytope" http://www.eurocg2016.usi.ch/sites/default/files/paper_76.pdf (which appeared in the conference EuroCG 2016, Lugano, Switzerland, March 30-April 1, 2016)

For special cases such as associahedra, specialized algorithms are available - e.g., C. Lange, Discrete & Computational Geometry volume 50, pages 903–939 (2013) https://link.springer.com/article/10.1007/s00454-013-9546-5

Also G. Fourier, Marked poset polytopes: Minkowski sums, indecomposables, and unimodular equivalence, https://www.sciencedirect.com/science/article/abs/pii/S0022404915001942

J. Ivanović, GEOMETRICAL REALISATIONS OF THE SIMPLE PERMUTOASSOCIAHEDRON BY MINKOWSKI SUMS, https://www.jstor.org/stable/26964946

T. Michiels and R. Cools. Decomposing the secondary Cayley polytope. Discr. Comput. Geometry, 23:367–380, 2000.

CC: @VivianePons @mkoeppe @jplab @mo271

Component: geometry

Keywords: polytope, Minkowski sum, Minkowski decomposition, days82

Issue created by migration from https://trac.sagemath.org/ticket/22181

[videlec]

comment:2

Note that polymake already has a C++ implementation following Fukada's "From the zonotope construction to the Minkowski addition of convex polytopes" (2004).

[mkoeppe]

comment:4

accessing polymake is now easy with #22683: backend_polymake for Polyhedron

[mkoeppe]

Description changed:

--- 
+++ 
@@ -1,2 +1,4 @@
 I plan to add code for Minkowski Decomposition of Polytopes
 based on the algorithm in "On the space of Minkowski summands of a convex polytope" [http://www.eurocg2016.usi.ch/sites/default/files/paper_76.pdf](http://www.eurocg2016.usi.ch/sites/default/files/paper_76.pdf) (which appeared in the conference EuroCG 2016, Lugano, Switzerland, March 30-April 1, 2016)
+
+For special cases such as associahedra, specialized algorithms are available - e.g., Lange, Discrete & Computational Geometry volume 50, pages 903–939 (2013) https://link.springer.com/article/10.1007/s00454-013-9546-5

[mkoeppe]

comment:7

@sagetrac-etzanaki - has anything been implemented?

[mkoeppe]

Description changed:

--- 
+++ 
@@ -1,4 +1,6 @@
 I plan to add code for Minkowski Decomposition of Polytopes
 based on the algorithm in "On the space of Minkowski summands of a convex polytope" [http://www.eurocg2016.usi.ch/sites/default/files/paper_76.pdf](http://www.eurocg2016.usi.ch/sites/default/files/paper_76.pdf) (which appeared in the conference EuroCG 2016, Lugano, Switzerland, March 30-April 1, 2016)

-For special cases such as associahedra, specialized algorithms are available - e.g., Lange, Discrete & Computational Geometry volume 50, pages 903–939 (2013) https://link.springer.com/article/10.1007/s00454-013-9546-5
+For special cases such as associahedra, specialized algorithms are available - e.g., C. Lange, Discrete & Computational Geometry volume 50, pages 903–939 (2013) https://link.springer.com/article/10.1007/s00454-013-9546-5
+
+Also G. Fourier, Marked poset polytopes: Minkowski sums, indecomposables, and unimodular equivalence, https://www.sciencedirect.com/science/article/abs/pii/S0022404915001942

[mkoeppe]

Description changed:

--- 
+++ 
@@ -4,3 +4,5 @@
 For special cases such as associahedra, specialized algorithms are available - e.g., C. Lange, Discrete & Computational Geometry volume 50, pages 903–939 (2013) https://link.springer.com/article/10.1007/s00454-013-9546-5

 Also G. Fourier, Marked poset polytopes: Minkowski sums, indecomposables, and unimodular equivalence, https://www.sciencedirect.com/science/article/abs/pii/S0022404915001942
+
+J. Ivanović, GEOMETRICAL REALISATIONS OF THE SIMPLE PERMUTOASSOCIAHEDRON BY MINKOWSKI SUMS, https://www.jstor.org/stable/26964946

[mkoeppe]

Description changed:

--- 
+++ 
@@ -6,3 +6,7 @@
 Also G. Fourier, Marked poset polytopes: Minkowski sums, indecomposables, and unimodular equivalence, https://www.sciencedirect.com/science/article/abs/pii/S0022404915001942

 J. Ivanović, GEOMETRICAL REALISATIONS OF THE SIMPLE PERMUTOASSOCIAHEDRON BY MINKOWSKI SUMS, https://www.jstor.org/stable/26964946
+
+T. Michiels and R. Cools. Decomposing the secondary
+Cayley polytope. Discr. Comput. Geometry,
+23:367–380, 2000.