Decomposition of polytopes and polynomials

Simple item page
dc.creatorGao, S.
dc.creatorLauder, A. G. B.
dc.date2000-12-12
dc.date.accessioned2026-07-07T04:39:12Z
dc.date.available2026-07-07T04:39:12Z
dc.descriptionMotivated 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.
dc.description29 pages, to appear in Discrete and Computational Geometry
dc.identifierhttps://arxiv.org/abs/math/0012099
dc.identifierhttp://arxiv.org/abs/math/0012099
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/60562
dc.subjectCombinatorics
dc.subject52B20, 12Y05
dc.titleDecomposition of polytopes and polynomials
dc.typetext

Files

Collections

arXiv