{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T09:38:16Z","timestamp":1773740296965,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,10]]},"DOI":"10.1007\/s00453-008-9219-6","type":"journal-article","created":{"date-parts":[[2008,8,14]],"date-time":"2008-08-14T17:54:49Z","timestamp":1218736489000},"page":"329-345","source":"Crossref","is-referenced-by-count":50,"title":["Exact Minkowksi Sums of Polyhedra and\u00a0Exact and\u00a0Efficient Decomposition of Polyhedra into\u00a0Convex\u00a0Pieces"],"prefix":"10.1007","volume":"55","author":[{"given":"Peter","family":"Hachenberger","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,8,15]]},"reference":[{"key":"9219_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":"2","key":"9219_CR2","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF02123007","volume":"10","author":"B. Aronov","year":"1990","unstructured":"Aronov, B., Sharir, M.: Triangles in space or building (and analyzing) castles in the air. Combinatorica 10(2), 137\u2013173 (1990)","journal-title":"Combinatorica"},{"issue":"2","key":"9219_CR3","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1137\/0221025","volume":"21","author":"C.L. Bajaj","year":"1992","unstructured":"Bajaj, C.L., Dey, T.K.: Convex decomposition of polyhedra and robustness. SIAM J. Comput. 21(2), 339\u2013364 (1992)","journal-title":"SIAM J. Comput."},{"key":"9219_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1007\/978-3-540-75520-3_57","volume-title":"15th European Symposium on Algorithms, ESA\u00a007","author":"E. Berberich","year":"2007","unstructured":"Berberich, E., Fogel, E., Halperin, D., Mehlhorn, K., Wein, R.: Sweeping and maintaining two-dimensional arrangements on surfaces: A\u00a0first step. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) 15th European Symposium on Algorithms, ESA\u00a007, Eilat, Israel, October 2007. Lecture Notes in Computer Science, vol.\u00a04698, pp.\u00a0645\u2013656. Springer, Berlin (2007)"},{"key":"9219_CR5","unstructured":"The CGAL Homepage. http:\/\/www.cgal.org\/"},{"issue":"3","key":"9219_CR6","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1137\/0213031","volume":"13","author":"B. Chazelle","year":"1984","unstructured":"Chazelle, B.: Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm. SIAM J. Comput. 13(3), 488\u2013507 (1984)","journal-title":"SIAM J. Comput."},{"issue":"5\u20136","key":"9219_CR7","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/S0925-7721(96)00024-7","volume":"7","author":"B. Chazelle","year":"1997","unstructured":"Chazelle, B., Dobkin, D., Shouraboura, N., Tal, A.: Strategies for polyhedral surface decomposition: an experimental study. Comput. Geom.: Theory Appl. 7(5\u20136), 327\u2013342 (1997)","journal-title":"Comput. Geom.: Theory Appl."},{"key":"9219_CR8","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/BF02187807","volume":"5","author":"B. Chazelle","year":"1990","unstructured":"Chazelle, B., Palios, L.: Triangulating a nonconvex polytope. Discrete Comput. Geom. 5, 505\u2013526 (1990)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9219_CR9","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02716578","volume":"15","author":"M. Berg de","year":"1996","unstructured":"de Berg, M., Guibas, L.J., Halperin, D.: Vertical decompositions for triangles in 3-space. Discrete Comput. Geom. 15(1), 35\u201361 (1996)","journal-title":"Discrete Comput. Geom."},{"key":"9219_CR10","doi-asserted-by":"crossref","unstructured":"Ehmann, S.A., Lin, M.C.: Accurate and fast proximity queries between polyhedra using convex surface decomposition. In: Computer Graphics Forum, Proc. Eurographics 2001, vol.\u00a020(3), pp.\u00a0500\u2013510 (2001)","DOI":"10.1111\/1467-8659.00543"},{"key":"9219_CR11","doi-asserted-by":"crossref","unstructured":"Elber, G., Kim, M.-S. (eds.): Special Issue of Computer Aided Design: Offsets, Sweeps and Minkowski Sums, vol.\u00a031 (1999)","DOI":"10.1016\/S0010-4485(99)00012-3"},{"key":"9219_CR12","unstructured":"Evans, R.C., O\u2019Connor, M.A., Rossignac, J.R.: Construction of Minkowski sums and derivatives morphological combinations of arbitrary polyhedra in CAD\/CAM systems. US Patent 5159512 (1992)"},{"issue":"11","key":"9219_CR13","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."},{"key":"9219_CR14","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Ramshaw, L., Stolfi, J.: A kinetic framework for computational geometry. In: 24th Symposium on Foundations of Computer Science (FOCS), pp.\u00a0100\u2013111 (1983)","DOI":"10.1109\/SFCS.1983.1"},{"issue":"1\u20132","key":"9219_CR15","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.comgeo.2006.11.009","volume":"38","author":"P. Hachenberger","year":"2007","unstructured":"Hachenberger, P., Kettner, L., Mehlhorn, K.: Boolean operations on 3D selective Nef complexes: Data structure, algorithms, optimized implementation and experiments. Comput. Geom.: Theory Appl. 38(1\u20132), 64\u201399 (2007)","journal-title":"Comput. Geom.: Theory Appl."},{"issue":"5\u20136","key":"9219_CR16","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0961-3552(91)90036-4","volume":"13","author":"B. Joe","year":"1991","unstructured":"Joe, B.: A software package for the generation of meshes using geometric algorithms. Adv. Eng. Softw. Workst. 13(5\u20136), 325\u2013331 (1991)","journal-title":"Adv. Eng. Softw. Workst."},{"issue":"1","key":"9219_CR17","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0097-8493(92)90077-9","volume":"16","author":"A. Kaul","year":"1992","unstructured":"Kaul, A., Rossignac, J.R.: Solid-interpolating deformations: Construction and animation of pips. Computers &\u00a0Graphics 16(1), 107\u2013115 (1992)","journal-title":"Computers &\u00a0Graphics"},{"key":"9219_CR18","doi-asserted-by":"crossref","unstructured":"Kim, Y.J., Otaduy, M.A., Lin, M.C., Manocha, D.: Fast penetration depth computation using rasterization hardware and hierarchical refinement. In: Proc. of Workshop on Algorithmic Foundations of Robotics (2002)","DOI":"10.1145\/777847.777856"},{"key":"9219_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-4022-9","volume-title":"Robot Motion Planning","author":"J.-C. Latombe","year":"1991","unstructured":"Latombe, J.-C.: Robot Motion Planning. Kluwer Academic, Norwell (1991)"},{"key":"9219_CR20","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, pp.\u00a0787\u2013808. CRC Press LLC, Boca Raton (2004), Chap.\u00a035"},{"key":"9219_CR21","volume-title":"Art Gallery Theorems and Algorithms","author":"J. O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press, New York (1987)"},{"key":"9219_CR22","unstructured":"Rossignac, J.R.: Private communication (2007)"},{"issue":"2","key":"9219_CR23","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0167-8396(86)90017-8","volume":"3","author":"J.R. Rossignac","year":"1986","unstructured":"Rossignac, J.R., Requicha, A.A.G.: Offsetting operations in solid modelling. Comput. Aided Geom. Des. 3(2), 129\u2013148 (1986)","journal-title":"Comput. Aided Geom. Des."},{"key":"9219_CR24","unstructured":"R\u00f6ssl, C., Kobbelt, L., Seidel, H.-P.: Extraction of feature lines on triangulated surfaces using morphological operators. In: Proc. of the 2000 AAAI Symp. (2000)"},{"key":"9219_CR25","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1145\/513400.513437","volume-title":"SCG\u00a0\u201902: Proceedings of the eighteenth annual symposium on Computational geometry","author":"H. Shaul","year":"2002","unstructured":"Shaul, H., Halperin, D.: Improved construction of vertical decompositions of three-dimensional arrangements. In: SCG\u00a0\u201902: Proceedings of the eighteenth annual symposium on Computational geometry, New York, NY, USA, pp.\u00a0283\u2013292. ACM Press, New York (2002)"},{"issue":"4","key":"9219_CR26","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/j.gmod.2005.11.003","volume":"68","author":"G. Varadhan","year":"2006","unstructured":"Varadhan, G., Manocha, D.: Accurate Minkowski sum approximation of polyhedral models. Graph. Models 68(4), 343\u2013355 (2006)","journal-title":"Graph. Models"},{"key":"9219_CR27","doi-asserted-by":"crossref","unstructured":"Wein, R.: Exact and efficient construction of planar Minkowski sums using the convolution method. In: 14th European Symposium on Algorithms (ESA\u00a006), pp.\u00a0829\u2013840 (2006)","DOI":"10.1007\/11841036_73"},{"issue":"1","key":"9219_CR28","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1147\/rd.241.0064","volume":"24","author":"M.A. Wesley","year":"1980","unstructured":"Wesley, M.A., Lozano-Prez, T., Lieberman, L.I., Lavin, M.A., Grossman, D.D.: A\u00a0geometric modeling system for automated mechanical assembly. IBM J. Res. Dev. 24(1), 64\u201374 (1980)","journal-title":"IBM J. Res. Dev."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9219-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T10:40:52Z","timestamp":1557744052000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9219-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8,15]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["9219"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9219-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8,15]]}}}