{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T22:14:12Z","timestamp":1791238452820,"version":"4.1.0"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[1993,5]]},"abstract":"<jats:p>This paper deals with a problem from computational convexity and its application to computer algebra. This paper determines the complexity of computing the Minkowski sum of k convex polytopes in $\\mathbb{R}^d $, which are presented either in terms of vertices or in terms of facets. In particular, if the dimension d is fixed, the authors obtain a polynomial time algorithm for adding k polytopes with up to n vertices. The second part of this paper introduces dynamic versions of Buchberger\u2019s Gr\u00f6bner bases algorithm for polynomial ideals. Using the Minkowski addition of Newton polytopes, the authors show that the following problem can be solved in polynomial time for any finite set of polynomials $\\mathcal{T} \\subset K [ x_1 , \\ldots ,x_d ]$, where d is fixed: Does there exist a term order $\\tau $ such that $\\mathcal{T}$ is a Gr\u00f6bner basis for its ideal with respect to $\\tau $? If not, find an optimal term order for $\\mathcal{T}$ with respect to a natural Hilbert function criterion.<\/jats:p>","DOI":"10.1137\/0406019","type":"journal-article","created":{"date-parts":[[2005,2,23]],"date-time":"2005-02-23T08:05:53Z","timestamp":1109145953000},"page":"246-269","source":"Crossref","is-referenced-by-count":150,"title":["Minkowski Addition of Polytopes: Computational Complexity and Applications to Gr\u00f6bner Bases"],"prefix":"10.1137","volume":"6","author":[{"given":"Peter","family":"Gritzmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bernd","family":"Sturmfels","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-6303-2_2"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.3.445"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(88)80043-9"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01389151"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0747-7171(92)90024-X"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02123011"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-47404-0"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01844169"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"B. Buchberger, N. K. Bose, Gr\u00f6bner bases\u2014an algorithmic method in polynomial ideal theory, Multidimensional Systems Theory, Chapter 6, D. Reidel, 1985","DOI":"10.1007\/978-94-009-5225-6_6"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-7074-1_3"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1943.11991447"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.3.381"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0215024"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0038185"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584082"},{"key":"R17","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"R18","unstructured":"P. Gianni, Efficient computation of zero-dimensional Gr\u00f6bner bases by change of ordering, presented at the Conference on Computers and Commutative Algebra (COCOA II), Genova, Italy, 1989, June0805.13007"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9617-8_1"},{"key":"R20","unstructured":"P. Gritzmann, V. Klee, Computational aspects of zonotopes and their polars, in preparation"},{"key":"R21","volume-title":"Convex polytopes","author":"Gr\u00fcnbaum Branko","year":"1967"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187878"},{"key":"R23","volume-title":"New Trends in Discrete and Computational Geometry","author":"Korneenko N. M.","year":"1992"},{"key":"R24","unstructured":"J. Matou\u0161ek, O. Schwarzkopf, Linear optimization queries, Math. Tech. Report FU Berlin, B91-19, 1991"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(82)90048-2"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300002850"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322418"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(88)80042-7"},{"key":"R29","first-page":"98","volume":"30","author":"Ostrowski A.","year":"1921","journal-title":"Jahres-berichte Deutsche Math. Verein"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01836524"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580724"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(86)80019-0"},{"key":"R33","unstructured":"R. Seidel, Masters Thesis, Output-Size Sensitive Algorithms for Constructive Problems in Computational Geometry, Ph.D. dissertation, Department of Computer Science, Cornell University, Ithaca, NY, 1987"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90017-3"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580859"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-51082-6_96"},{"key":"R37","volume":"1","author":"Zaslavsky Thomas","year":"1975","journal-title":"Mem. Amer. Math. Soc."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0406019","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:14:02Z","timestamp":1787318042000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0406019"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,5]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,5]]}},"alternative-id":["10.1137\/0406019"],"URL":"https:\/\/doi.org\/10.1137\/0406019","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,5]]}}}