Opened 5 years ago

Last modified 3 months ago

#22181 new enhancement

Implement Minkowski decomposition of polytopes

Reported by: etzanaki Owned by:
Priority: major Milestone: sage-9.5
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:

Status badges

Description (last modified by mkoeppe)

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

  1. Ivanović, GEOMETRICAL REALISATIONS OF THE SIMPLE PERMUTOASSOCIAHEDRON BY MINKOWSKI SUMS, https://www.jstor.org/stable/26964946
  1. Michiels and R. Cools. Decomposing the secondary

Cayley polytope. Discr. Comput. Geometry, 23:367–380, 2000.

Change History (11)

comment:1 Changed 5 years ago by etzanaki

  • Cc mkoeppe added

comment:2 Changed 5 years ago by vdelecroix

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

comment:3 Changed 5 years ago by jipilab

  • Cc jipilab added

comment:4 Changed 5 years ago by mkoeppe

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

comment:5 Changed 4 years ago by moritz

  • Cc moritz added

comment:6 Changed 4 months ago by mkoeppe

  • Description modified (diff)
  • Milestone changed from sage-7.6 to sage-9.4

comment:7 Changed 4 months ago by mkoeppe

@etzanaki - has anything been implemented?

comment:8 Changed 4 months ago by mkoeppe

  • Description modified (diff)

comment:9 Changed 4 months ago by mkoeppe

  • Description modified (diff)

comment:10 Changed 4 months ago by mkoeppe

  • Description modified (diff)

comment:11 Changed 3 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5
Note: See TracTickets for help on using tickets.