{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,19]],"date-time":"2026-04-19T20:35:38Z","timestamp":1776630938433,"version":"3.51.2"},"reference-count":111,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"8","license":[{"start":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T00:00:00Z","timestamp":1627776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T00:00:00Z","timestamp":1627776000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T00:00:00Z","timestamp":1627776000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Visual. Comput. Graphics"],"published-print":{"date-parts":[[2021,8,1]]},"DOI":"10.1109\/tvcg.2020.2976922","type":"journal-article","created":{"date-parts":[[2020,2,28]],"date-time":"2020-02-28T22:29:07Z","timestamp":1582928947000},"page":"3377-3396","source":"Crossref","is-referenced-by-count":8,"title":["A Review of Methods to Compute Minkowski Operations for Geometric Overlap Detection"],"prefix":"10.1109","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6671-2412","authenticated-orcid":false,"given":"Wesley","family":"Cox","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lyndon","family":"While","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5415-0544","authenticated-orcid":false,"given":"Mark","family":"Reynolds","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4485(97)00074-2"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187878"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/1049-9660(91)90078-4"},{"key":"ref32","first-page":"50","article-title":"Geometry, shoemaking and the milk tray problem","volume":"123","author":"cuninghame-green","year":"1989","journal-title":"New Sci"},{"key":"ref31","author":"gr\u00fcnbaum","year":"1967","journal-title":"Convex Polytopes"},{"key":"ref30","author":"benson","year":"1966","journal-title":"Euclidean Geometry and Convexity"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90069-5"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1985.1087334"},{"key":"ref35","article-title":"Local and global techniques for motion planning","author":"donald","year":"1984"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1016\/0097-8493(93)90023-3"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9159-1"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02712873"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573985"},{"key":"ref20","first-page":"1","article-title":"Collision detection","author":"kim","year":"2018","journal-title":"Humanoid Robotics A Reference"},{"key":"ref22","author":"needham","year":"1998","journal-title":"Visual Complex Analysis"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1109\/70.388783"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461916"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_73"},{"key":"ref101","first-page":"91","article-title":"The complexity of a single face of a minkowski sum","author":"har-peled","year":"1995","journal-title":"Proc 7th Can Conf Comput Geometry"},{"key":"ref26","article-title":"Analytical design of compensators and computational geometry","author":"najfeld","year":"1978"},{"key":"ref100","doi-asserted-by":"publisher","DOI":"10.1115\/1.4005776"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201337"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(00)00021-6"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.1"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1988.12304"},{"key":"ref58","article-title":"Extracting the Minkowski sum boundary from the reduced convolution","author":"behar","year":"2010","journal-title":"Proc 20th Annu Fall Workshop Comput Geometry"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2004.11.005"},{"key":"ref56","article-title":"Minimizing waste in the 2-dimensional cutting stock problem","author":"dean","year":"2002"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2602255"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2006.02.026"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54233-7_172"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1145\/237218.237374"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1996.506915"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2004.1260767"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190153"},{"key":"ref6","article-title":"The optimum two-dimensional allocation of irregular, multiply-connected shapes with linear, logical and geometric constraints","author":"adamowicz","year":"1969"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2016.05.012"},{"key":"ref8","article-title":"An approach to the two dimensional, irregular, cutting stock problem","author":"art","year":"1966"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2011.06.021"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676196"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2013.03.003"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1986.4767773"},{"key":"ref45","article-title":"Computing Minkowski sums","author":"kaul","year":"1993"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5979992"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1994.351105"},{"key":"ref42","article-title":"Minkowski sum construction and other applications of arrangements of geodesic arcs on the sphere","author":"fogel","year":"2009"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972863.1"},{"key":"ref44","first-page":"5105","article-title":"The algorithm for computing exact Minkowski sum of 3D convex polyhedral","volume":"11","author":"guo","year":"2010","journal-title":"Int J Innovative Comput Inf Control"},{"key":"ref43","first-page":"1401","article-title":"Optimization algorithm for computing exact Minkowski sum of 3D convex polyhedra","volume":"4","author":"guo","year":"2008","journal-title":"Int J Innovative Comput Inf Control"},{"key":"ref73","article-title":"Applying meta-heuristic algorithms to the nesting problem utilising the no fit polygon","author":"kendall","year":"2000"},{"key":"ref72","article-title":"Mathematical treatments of some apparel marking and cutting problems","author":"konopasek","year":"1981"},{"key":"ref71","article-title":"Optimization in computer-aided pattern packing","author":"mahadevan","year":"1984"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1145\/1839778.1839783"},{"key":"ref76","article-title":"Polyhedral tracings and their convolution","author":"basch","year":"1996","journal-title":"Proc Workshop Algorithmic Found Robot"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61680-2_64"},{"key":"ref74","article-title":"Novel heuristic and metaheuristic approaches to cutting and packing","author":"whitwell","year":"2004"},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.03.011"},{"key":"ref78","doi-asserted-by":"publisher","DOI":"10.1145\/323233.323244"},{"key":"ref79","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187683"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1989230100051"},{"key":"ref62","article-title":"Analysis and planning of planar manipulation tasks","author":"brost","year":"1991"},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1989.99985"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675432"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2018.06.005"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2012.10.016"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696509"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1145\/1839778.1839782"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1137\/0215024"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90051-X"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01609.x"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1976.16"},{"key":"ref109","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21963-9_31"},{"key":"ref95","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.11.009"},{"key":"ref108","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2008.06.006"},{"key":"ref94","doi-asserted-by":"publisher","DOI":"10.1137\/0213031"},{"key":"ref107","first-page":"401","article-title":"A simple method for computing Minkowski sum boundary in 3D using collision detection","author":"lien","year":"2010","journal-title":"Algorithmic Foundations of Robotics VIII"},{"key":"ref93","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9219-6"},{"key":"ref106","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2011.6094482"},{"key":"ref92","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-005-1206-y"},{"key":"ref105","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2015.04.012"},{"key":"ref91","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(95)00021-H"},{"key":"ref104","article-title":"Rapidly-exploring random trees: Progress and prospects","author":"lavalle","year":"2000","journal-title":"Algorithmic and Computational Robotics New Directions"},{"key":"ref90","article-title":"Compaction algorithms for non-convex polygons and their applications","author":"li","year":"1994"},{"key":"ref103","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1060.0293"},{"key":"ref102","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1090.0770"},{"key":"ref111","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2013.08.021"},{"key":"ref110","doi-asserted-by":"publisher","DOI":"10.3722\/cadaps.2013.475-487"},{"key":"ref98","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2005.11.003"},{"key":"ref99","doi-asserted-by":"publisher","DOI":"10.1145\/37402.37422"},{"key":"ref96","volume":"1","author":"nef","year":"1978","journal-title":"Beiträge zur Theorie der Polyeder mit Anwendungen in der Computergraphik"},{"key":"ref97","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2015.06.016"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1080\/02331939308843904"},{"key":"ref11","author":"serra","year":"1982","journal-title":"Image Analysis and Mathematical Morphology"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2010.01770.x"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"ref14","article-title":"Octree encoding: A new technique for the representation, manipulation and display of arbitrary 3-D objects by computer","author":"meagher","year":"1980"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1145\/358105.358195"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.01.025"},{"key":"ref82","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00041-4"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.11.063"},{"key":"ref81","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187779"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.1530387"},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.1137\/0214056"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.1420105"},{"key":"ref83","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2635"},{"key":"ref80","article-title":"A fast algorithm for boolean mask operations","author":"ottmann","year":"1982"},{"key":"ref89","first-page":"235","article-title":"The decomposition of polygons into convex parts","volume":"1","author":"greene","year":"1983","journal-title":"Comput Geometry"},{"key":"ref85","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/B978-0-444-87806-9.50009-8","article-title":"Optimal convex decompositions","author":"chazelle","year":"1985","journal-title":"Computational Geometry"},{"key":"ref86","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574002"},{"key":"ref87","article-title":"Robust and efficient construction of planar Minkowski sums","author":"flato","year":"2000"},{"key":"ref88","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574703"}],"container-title":["IEEE Transactions on Visualization and Computer Graphics"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/2945\/9468994\/09018075.pdf?arnumber=9018075","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,10]],"date-time":"2022-05-10T14:51:32Z","timestamp":1652194292000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/9018075\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,1]]},"references-count":111,"journal-issue":{"issue":"8"},"URL":"https:\/\/doi.org\/10.1109\/tvcg.2020.2976922","relation":{},"ISSN":["1077-2626","1941-0506","2160-9306"],"issn-type":[{"value":"1077-2626","type":"print"},{"value":"1941-0506","type":"electronic"},{"value":"2160-9306","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,1]]}}}