Decomposition of polytopes and polynomials
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...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2001
|
| _version_ | 1797079634019352576 |
|---|---|
| author | Gao, S Lauder, A |
| author_facet | Gao, S Lauder, A |
| author_sort | Gao, S |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T00:48:42Z |
| format | Journal article |
| id | oxford-uuid:859af7e1-97fb-4159-a518-df44bf40aea5 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:48:42Z |
| publishDate | 2001 |
| record_format | dspace |
| spelling | oxford-uuid:859af7e1-97fb-4159-a518-df44bf40aea52022-03-26T21:58:40ZDecomposition of polytopes and polynomialsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:859af7e1-97fb-4159-a518-df44bf40aea5EnglishSymplectic Elements at Oxford2001Gao, SLauder, AMotivated 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. |
| spellingShingle | Gao, S Lauder, A Decomposition of polytopes and polynomials |
| title | Decomposition of polytopes and polynomials |
| title_full | Decomposition of polytopes and polynomials |
| title_fullStr | Decomposition of polytopes and polynomials |
| title_full_unstemmed | Decomposition of polytopes and polynomials |
| title_short | Decomposition of polytopes and polynomials |
| title_sort | decomposition of polytopes and polynomials |
| work_keys_str_mv | AT gaos decompositionofpolytopesandpolynomials AT laudera decompositionofpolytopesandpolynomials |