Decomposition of polytopes and polynomials

2000/12/12 by S. Gao, Shuhong Gao, Gao, S. +3 · 2 citations
Computer Science · Mathematics · #12Y05 #52B20 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Cryptography and Data Security #FOS: Mathematics #Polynomial and algebraic computation #math.CO #msc:12Y05 #msc:52B20

paper · pdf · doi:10.48550/arxiv.math/0012099

29 pages, to appear in Discrete and Computational Geometry

arxiv created 2000/12/12 · openalex publication_date 2000/12/12 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Motivated by a connection with the factorization of multivariate polynomials, we study integral convex polytopes and their integral decompositions in the sense of the Minkowski sum. We first show that deciding decomposability of integral polygons is NP-complete then present a pseudo-polynomial time algorithm for decomposing polygons. For higher dimensional polytopes, we give a heuristic algorithm which is based upon projections and uses randomization. Applications of our algorithm include absolute irreducibility testing and factorization of polynomials via their Newton polytopes.

Cited by

• The graph of implicit edge dependencies for indecomposability and beyond
• Signed Minkowski decompositions of convex polygons into minimum simplices and factorization of max-plus functions

Related

• Decomposition Methods for Nonlinear Optimization and Data Mining
• Improvements of convex-dense factorization of bivariate polynomials
• Integer decomposition property of dilated polytopes
• More indecomposable polyhedra
• Some Algorithmic Problems in Polytope Theory