Minkowski length of 3D lattice polytopes. (English) Zbl 1262.52009
The Minkowski length \(L(P)\) of a lattice polytope \(P\) is the largest number of non-trivial primitive segments whose Minkowski sum lies in \(P\). In this paper the authors give a polytime algorithm to compute \(L(P)\) in three-dimensional case. Further they study the three-dimensional polytopes with small Minkowski length. In particular, it is shown that if \(Q\), a subpolytope of \(P\), is the Minkowski sum of \(L=L(P)\) lattice polytopes \(Q_i\), each of Minkowski length 1, then the total number of interior points of all the summands \(Q_1,\dots, Q_L\) is at most 4. The methods of the work differ substantially from those used in the two-dimensional case.
General remark: The Minkowski length represents the largest possible number of factors in a factorization of polynomials with exponent vectors in \(P\), and shows up in lower bounds for the minimal distance of toric codes.
General remark: The Minkowski length represents the largest possible number of factors in a factorization of polynomials with exponent vectors in \(P\), and shows up in lower bounds for the minimal distance of toric codes.
Reviewer: Oleg Karpenkov (Liverpool)
MSC:
| 52B20 | Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) |
Software:
polymakeReferences:
| [1] | Alexander, I.B.: Polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math. Oper. Res. 19, 769-779 (1994) · Zbl 0821.90085 · doi:10.1287/moor.19.4.769 |
| [2] | Gawrilow, E.; Joswig, M., Polymake: a framework for analyzing convex polytopes, Oberwolfach, 1997, Basel · Zbl 0960.68182 |
| [3] | Hansen, J. P., Toric surfaces and error-correcting codes, Guanajuato, 1998, Berlin · Zbl 1010.94014 · doi:10.1007/978-3-642-57189-3_12 |
| [4] | Kasprzyk, A.M.: Toric Fano three-folds with terminal singularities. Tohoku Math. J. (2) 58(1), 101-121 (2006) · Zbl 1118.14047 · doi:10.2748/tmj/1145390208 |
| [5] | Köppe, M.: A primal Barvinok algorithm based on irrational decompositions. SIAM J. Discrete Math. 21, 220-236 (2007) · Zbl 1135.05003 · doi:10.1137/060664768 |
| [6] | Little, J., Schenck, H.: Toric surface codes and Minkowski sums. SIAM J. Discrete Math. 20(4), 999-1014 (2006) (electronic) · Zbl 1131.14026 · doi:10.1137/050637054 |
| [7] | Newman, M.: Integral Matrices. Pure and Applied Mathematics, vol. 45. Academic Press, San Diego (1972) ISBN-13:978-0125178501, 224 pp. · Zbl 0254.15009 |
| [8] | Ruano, D.: On the parameters of r-dimensional toric codes. Finite Fields Appl. 13(4), 962-976 (2007) · Zbl 1210.94115 · doi:10.1016/j.ffa.2007.02.002 |
| [9] | Scarf, H.E.: Integral polyhedra in three space. Math. Oper. Res. 10(3), 403-438 (1985) · Zbl 0577.90054 · doi:10.1287/moor.10.3.403 |
| [10] | Soprunov, I., Soprunova, J.: Toric surface codes and Minkowski length of polygons. SIAM J. Discrete Math. 23(1), 384-400 (2008/09) · Zbl 1195.94088 · doi:10.1137/080716554 |
| [11] | Gaudinez, A., Outing, C., Vega, R.: Indecomposable polyhedra and toric codes. MSRI-UP 2009 Technical report, http://www.msri.org/web/msri/scientific/workshops/show/-/event/Wm491 45-57 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
