{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T14:50:37Z","timestamp":1776955837782,"version":"3.51.4"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,7,15]],"date-time":"2008-07-15T00:00:00Z","timestamp":1216080000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2008,10]]},"DOI":"10.1007\/s00454-008-9097-3","type":"journal-article","created":{"date-parts":[[2008,7,14]],"date-time":"2008-07-14T11:41:13Z","timestamp":1216035673000},"page":"469-479","source":"Crossref","is-referenced-by-count":81,"title":["On the Hardness of Computing Intersection, Union and\u00a0Minkowski Sum of Polytopes"],"prefix":"10.1007","volume":"40","author":[{"given":"Hans Raj","family":"Tiwary","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,7,15]]},"reference":[{"key":"9097_CR1","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/S0925-7721(96)00023-5","volume":"7","author":"D. Avis","year":"1997","unstructured":"Avis, D., Bremner, D., Seidel, R.: How good are convex hull algorithms? Comput. Geom. 7, 265\u2013301 (1997)","journal-title":"Comput. Geom."},{"key":"9097_CR2","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0167-6377(88)90058-2","volume":"7","author":"E. Balas","year":"1988","unstructured":"Balas, E.: On the convex hull of the union of certain polyhedra. Oper. Res. Lett. 7, 279\u2013283 (1988)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"9097_CR3","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/BF01582241","volume":"33","author":"R.M. Freund","year":"1985","unstructured":"Freund, R.M., Orlin, J.B.: On the complexity of four polyhedral set containment problems. Math. Program. 33(2), 139\u2013145 (1985)","journal-title":"Math. Program."},{"issue":"4","key":"9097_CR4","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.1016\/j.jsc.2003.08.007","volume":"38","author":"K. Fukuda","year":"2004","unstructured":"Fukuda, K.: From the zonotope construction to the Minkowski addition of convex polytopes. J. Symb. Comput. 38(4), 1261\u20131272 (2004)","journal-title":"J. Symb. Comput."},{"issue":"1\u20132","key":"9097_CR5","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/S0925-7721(01)00032-3","volume":"20","author":"K. Fukuda","year":"2001","unstructured":"Fukuda, K., Liebling, T.M., Lutolf, C.: Extended convex hull. Comput. Geom. 20(1\u20132), 13\u201323 (2001)","journal-title":"Comput. Geom."},{"key":"9097_CR6","unstructured":"Fukuda, K., Weibel, C.: Computing all faces of the Minkowski sum of $\\mathcal{V}$ -polytopes. In: Proceedings of the 17th Canadian Conference on Computational Geometry (2005)"},{"key":"9097_CR7","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/s00454-007-1310-2","volume":"37","author":"K. Fukuda","year":"2007","unstructured":"Fukuda, K., Weibel, C.: f-vectors of Minkowski additions of convex polytopes. Discrete Comput. Geom. 37, 503\u2013516 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"9097_CR8","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1137\/0406019","volume":"6","author":"P. Gritzmann","year":"1993","unstructured":"Gritzmann, P., Sturmfels, B.: Minkowski addition of polytopes: Computational complexity and applications to Grobner bases. SIAM J. Discrete Math. 6, 246\u2013269 (1993)","journal-title":"SIAM J. Discrete Math."},{"key":"9097_CR9","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, vol. 2. Springer, Berlin (1993)."},{"key":"9097_CR10","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0019-9","volume-title":"Convex Polytopes","author":"B. Gr\u00fcnbaum","year":"2003","unstructured":"Gr\u00fcnbaum, B.: Convex Polytopes, 2nd edn. Graduate Texts in Mathematics, vol. 221. Springer, Berlin (2003). Prepared by V. Kaibel, V.L. Klee, G.M. Ziegler","edition":"2"},{"issue":"2","key":"9097_CR11","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/s100970050003","volume":"2","author":"B. Huber","year":"2000","unstructured":"Huber, B., Rambau, J., Santos, F.: The Cayley trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings. J.\u00a0Eur. Math. Soc. 2(2), 179\u2013198 (2000)","journal-title":"J.\u00a0Eur. Math. Soc."},{"issue":"1\u20133","key":"9097_CR12","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/s00454-008-9050-5","volume":"39","author":"L. Khachiyan","year":"2008","unstructured":"Khachiyan, L., Boros, E., Borys, K., Elbassioni, K.M., Gurvich, V.: Generating all vertices of a polyhedron is hard. Discrete Comput. Geom. 39(1\u20133), 174\u2013190 (2008)","journal-title":"Discrete Comput. Geom."},{"key":"9097_CR13","first-page":"191","volume":"20","author":"L.G. Khachiyan","year":"1979","unstructured":"Khachiyan, L.G.: A polynomial algorithm in linear programming. Sov. Math. Dokl. 20, 191\u2013194 (1979)","journal-title":"Sov. Math. Dokl."},{"issue":"2","key":"9097_CR14","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1023\/A:1022497624378","volume":"3","author":"B. Strumfels","year":"1994","unstructured":"Strumfels, B.: On the Newton polytope of the resultant. J.\u00a0Algebr. Comb. 3(2), 207\u2013236 (1994)","journal-title":"J.\u00a0Algebr. Comb."},{"key":"9097_CR15","volume-title":"Fundamental Problems in Algorithmic Algebra","author":"C.K. Yap","year":"2000","unstructured":"Yap, C.K.: Fundamental Problems in Algorithmic Algebra. Oxford University Press, Oxford (2000)"},{"key":"9097_CR16","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-8431-1","volume-title":"Lectures on Polytopes","author":"G.M. Ziegler","year":"1995","unstructured":"Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, Berlin (1995)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-008-9097-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-008-9097-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-008-9097-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:35Z","timestamp":1559072855000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-008-9097-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,15]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["9097"],"URL":"https:\/\/doi.org\/10.1007\/s00454-008-9097-3","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,7,15]]}}}