Journal article icon

Journal article

Decomposition of polytopes and polynomials

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 ab...

Expand abstract
Publication status:
Published

Actions


Access Document


Publisher copy:
10.1007/s00454-001-0024-0

Authors


Lauder, AGB More by this author
Journal:
DISCRETE and COMPUTATIONAL GEOMETRY
Volume:
26
Issue:
1
Pages:
89-104
Publication date:
2001-07-05
DOI:
EISSN:
1432-0444
ISSN:
0179-5376
URN:
uuid:859af7e1-97fb-4159-a518-df44bf40aea5
Source identifiers:
147340
Local pid:
pubs:147340
Language:
English

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP