Opened 6 years ago
Last modified 6 months ago
#22181 new enhancement
Implement Minkowski decomposition of polytopes
Reported by: | etzanaki | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.7 |
Component: | geometry | Keywords: | polytope, Minkowski sum, Minkowski decomposition, days82 |
Cc: | vivianepons, mkoeppe, jipilab, moritz | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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
- Ivanović, GEOMETRICAL REALISATIONS OF THE SIMPLE PERMUTOASSOCIAHEDRON BY MINKOWSKI SUMS, https://www.jstor.org/stable/26964946
- Michiels and R. Cools. Decomposing the secondary
Cayley polytope. Discr. Comput. Geometry, 23:367–380, 2000.
Change History (13)
comment:1 Changed 6 years ago by
- Cc mkoeppe added
comment:2 Changed 5 years ago by
comment:3 Changed 5 years ago by
- Cc jipilab added
comment:4 Changed 5 years ago by
accessing polymake is now easy with #22683: backend_polymake for Polyhedron
comment:5 Changed 5 years ago by
- Cc moritz added
comment:6 Changed 14 months ago by
- Description modified (diff)
- Milestone changed from sage-7.6 to sage-9.4
comment:7 Changed 14 months ago by
@etzanaki - has anything been implemented?
comment:8 Changed 14 months ago by
- Description modified (diff)
comment:9 Changed 14 months ago by
- Description modified (diff)
comment:10 Changed 14 months ago by
- Description modified (diff)
comment:11 Changed 13 months ago by
- Milestone changed from sage-9.4 to sage-9.5
comment:12 Changed 8 months ago by
- Milestone changed from sage-9.5 to sage-9.6
comment:13 Changed 6 months ago by
- Milestone changed from sage-9.6 to sage-9.7
Note that polymake already has a C++ implementation following Fukada's "From the zonotope construction to the Minkowski addition of convex polytopes" (2004).