Decomposition of Polytopes and Polynomials |
| |
Authors: | S Gao A G B Lauder |
| |
Institution: | (1) Department of Mathematical Sciences, Clemson University, Clemson, SC 29634-0975, USA sgao@math.clemson.edu , US;(2) Mathematical Institute, Oxford University, Oxford OX1 3LB, England lauder@maths.ox.ac.uk, UK |
| |
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 algorithms include
absolute irreducibility testing and factorization of polynomials via their Newton polytopes.
Received December 2, 1999, and in revised form November 6, 2000. Online publication May 4, 2001. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|