{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:27:04Z","timestamp":1777444024498,"version":"3.51.4"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,4,8]],"date-time":"2009-04-08T00:00:00Z","timestamp":1239148800000},"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":[[2009,12]]},"DOI":"10.1007\/s00454-009-9159-1","type":"journal-article","created":{"date-parts":[[2009,4,7]],"date-time":"2009-04-07T15:40:02Z","timestamp":1239118802000},"page":"654-669","source":"Crossref","is-referenced-by-count":15,"title":["On the Exact Maximum Complexity of Minkowski Sums of Polytopes"],"prefix":"10.1007","volume":"42","author":[{"given":"Efi","family":"Fogel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Halperin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christophe","family":"Weibel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,4,8]]},"reference":[{"key":"9159_CR1","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0925-7721(01)00041-4","volume":"21","author":"P.K. Agarwal","year":"2002","unstructured":"Agarwal, P.K., Flato, E., Halperin, D.: Polygon decomposition for efficient construction of Minkowski sums. Comput. Geom. Theory Appl. 21, 39\u201361 (2002)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"6","key":"9159_CR2","doi-asserted-by":"crossref","first-page":"1785","DOI":"10.1137\/S0097539794266602","volume":"26","author":"B. Aronov","year":"1997","unstructured":"Aronov, B., Sharir, M.: On translational motion planning of a convex polyhedron in 3-space. SIAM J. Comput. 26(6), 1785\u20131803 (1997)","journal-title":"SIAM J. Comput."},{"key":"9159_CR3","first-page":"171","volume-title":"Proceedings of 2nd Workshop on the Algorithmic Foundations of Robotics","author":"J. Basch","year":"1996","unstructured":"Basch, J., Guibas, L.J., Ramkumar, G.D., Ramshaw, L.: Polyhedral tracings and their convolution. In: Laumond, J.P., Overmars, M. (eds.) Proceedings of 2nd Workshop on the Algorithmic Foundations of Robotics, pp. 171\u2013184. A.K. Peters, Wellesley (1996)"},{"key":"9159_CR4","first-page":"619","volume-title":"Proceedings of International Conference on Computational Science Part I","author":"H. Bekker","year":"2001","unstructured":"Bekker, H., Roerdink, J.B.T.M.: An efficient algorithm to calculate the Minkowski sum of convex 3D polyhedra. In: Proceedings of International Conference on Computational Science Part I, pp. 619\u2013628. Springer, Berlin (2001)"},{"key":"9159_CR5","doi-asserted-by":"crossref","unstructured":"Cameron, S.A., Culley, R.K.: Determining the minimum translational distance between two convex polyhedra. In: Proceedings of IEEE International Conference on Robotics and Automation, pp.\u00a0591\u2013596 (1986)","DOI":"10.1109\/ROBOT.1986.1087645"},{"issue":"11","key":"9159_CR6","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1016\/j.cad.2007.05.017","volume":"39","author":"E. Fogel","year":"2007","unstructured":"Fogel, E., Halperin, D.: Exact and efficient construction of Minkowski sums of convex polyhedra with applications. Comput. Aided Des. 39(11), 929\u2013940 (2007)","journal-title":"Comput. Aided Des."},{"issue":"4","key":"9159_CR7","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."},{"key":"9159_CR8","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."},{"issue":"4","key":"9159_CR9","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/0097-8493(93)90023-3","volume":"17","author":"P.K. Ghosh","year":"1993","unstructured":"Ghosh, P.K.: A unified computational framework for Minkowski operations. Comput. Graph. 17(4), 357\u2013378 (1993)","journal-title":"Comput. Graph."},{"key":"9159_CR10","series-title":"LNCS","first-page":"174","volume-title":"Proceedings of 11th Annual European Symposium on Algorithms (ESA)","author":"M. Granados","year":"2003","unstructured":"Granados, M., Hachenberger, P., Hert, S., Kettner, L., Mehlhorn, K., Seel, M.: Boolean operations on 3D selective Nef complexes: Data structure, algorithms, and implementation. In: Proceedings of 11th Annual European Symposium on Algorithms (ESA). LNCS, vol. 2832, pp. 174\u2013186. Springer, Berlin (2003)"},{"issue":"2","key":"9159_CR11","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 Gr\u00f6bner bases. SIAM J. Discrete Math. 6(2), 246\u2013269 (1993)","journal-title":"SIAM J. Discrete Math."},{"key":"9159_CR12","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Ramshaw, L., Stolfi, J.: A kinetic framework for computational geometry. In: Proceedings of 24th Annual IEEE Symposium on the Foundations of Computer Science, pp. 100\u2013111 (1983)","DOI":"10.1109\/SFCS.1983.1"},{"key":"9159_CR13","first-page":"1065","volume-title":"Handbook of Discrete and Computational Geometry","author":"D. Halperin","year":"2004","unstructured":"Halperin, D., Kavraki, L., Latombe, J.-C.: Robotics. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 1065\u20131093. Chapman & Hall\/CRC, London (2004). Chap.\u00a048","edition":"2"},{"key":"9159_CR14","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1090\/S0273-0979-1992-00303-8","volume":"27","author":"C.D. Hodgson","year":"1992","unstructured":"Hodgson, C.D., Rivin, I., Smith, W.D.: A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere. Bull. (New Ser.) AMS 27, 246\u2013251 (1992)","journal-title":"Bull. (New Ser.) AMS"},{"key":"9159_CR15","unstructured":"Kaul, A., Rossignac, J.: Solid-interpolating deformations: Construction and animation of PIPs. In: Proceedings of European Computer Graphics Conference (Eurographics), pp. 493\u2013505 (1991)"},{"key":"9159_CR16","first-page":"787","volume-title":"Handbook of Discrete and Computational Geometry","author":"M.C. Lin","year":"2004","unstructured":"Lin, M.C., Manocha, D.: Collision and proximity queries. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 787\u2013807. Chapman & Hall\/CRC, London (2004). Chap.\u00a035","edition":"2"},{"key":"9159_CR17","first-page":"1037","volume-title":"Handbook of Discrete and Computational Geometry","author":"M. Sharir","year":"2004","unstructured":"Sharir, M.: Algorithmic motion planning. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 1037\u20131064. Chapman & Hall\/CRC, London (2004). Chap.\u00a047","edition":"2"},{"key":"9159_CR18","unstructured":"Weibel, C.: Minkowski sums. http:\/\/roso.epfl.ch\/cw\/poly\/public.php"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9159-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-009-9159-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9159-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T21:56:38Z","timestamp":1739051798000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-009-9159-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,8]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["9159"],"URL":"https:\/\/doi.org\/10.1007\/s00454-009-9159-1","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4,8]]}}}