Signed Minkowski decompositions of convex polygons into minimum simplices and factorization of max-plus functions

2025/06/26 by Kitagawa, Soujun
#15A80 #52B20 #52C05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2506.20999

Abstract

Signed Minkowski decomposition is an expression of a polytope as a Minkowski sum and difference of smaller polytopes. Signed Minkowski decompositions of a polytope can be interpreted as factorizations of a max-plus (tropical) function. We review two relations about Minkowski decompositions, and we prove that any 2-dimensional integral polytopes (polygons) have a signed Minkowski decomposition which consists of integral points, integral line segments of length 1, and integral triangles of area 1/2. From this result, we also obtain that any max-plus functions with two variables and integer coefficients can be expressed as a set of specified form of simpler max-plus functions.

Citations

• Decomposition Polyhedra of Piecewise Linear Functions
• Representing Piecewise Linear Functions by Functions with Small Arity
• Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums
• Generalized permutahedra: Minkowski linear functionals and Ehrhart positivity
• Tropical Geometry of Deep Neural Networks
• The solution to the initial value problem for the ultradiscrete Somos-4 and 5 equations
• The integral polytope group
• The Grothendieck group of polytopes and norms
• Permutohedra, associahedra, and beyond
• Decomposition of polytopes and polynomials

Related

• Minkowski sum of polytopes and its normality
• Decomposition of an Integrally Convex Set into a Minkowski Sum of Bounded and Conic Integrally Convex Sets
• Decomposition of polytopes and polynomials
• Computing the Minkowski Sum of Convex Polytopes in \Re^d
• A linear equation for Minkowski sums of polytopes relatively in general position