{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:46:57Z","timestamp":1757314017824},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T00:00:00Z","timestamp":1594598400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T00:00:00Z","timestamp":1594598400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2020,11]]},"DOI":"10.1007\/s10589-020-00211-0","type":"journal-article","created":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T19:02:35Z","timestamp":1594666955000},"page":"465-490","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["The distance between convex sets with Minkowski sum structure: application to collision detection"],"prefix":"10.1007","volume":"77","author":[{"given":"Xiangfeng","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junping","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenxing","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,13]]},"reference":[{"key":"211_CR1","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/S0377-2217(98)00370-1","volume":"120","author":"MD Aliyu","year":"2000","unstructured":"Aliyu, M.D.: A vertex algorithm for collision detection. Eur. J. Oper. Res. 120, 174\u2013180 (2000)","journal-title":"Eur. J. Oper. Res."},{"key":"211_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-9467-7","volume-title":"Convex Analysis and Monotone Operator Theory in Hilbert Spaces","author":"HH Bauschke","year":"2011","unstructured":"Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011)"},{"key":"211_CR3","volume-title":"Convex Analysis and Optimization","author":"DP Bertsekas","year":"2003","unstructured":"Bertsekas, D.P.: Convex Analysis and Optimization. Athena Scientific, Belmont (2003)"},{"key":"211_CR4","volume-title":"Parallel and Distributed Computation: Numerical Methods","author":"DP Bertsekas","year":"1989","unstructured":"Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, Upper Saddle River (1989)"},{"key":"211_CR5","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1214\/aoap\/1075828053","volume":"14","author":"K B\u00f6r\u00f6czky","year":"2004","unstructured":"B\u00f6r\u00f6czky, K., Reitzner, M.: Approximation of smooth convex bodies by random circumscribed polytopes. Ann. Appl. Probab. 14, 239\u2013273 (2004)","journal-title":"Ann. Appl. Probab."},{"key":"211_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000016","volume":"3","author":"S Boyd","year":"2011","unstructured":"Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3, 1\u2013122 (2011)","journal-title":"Found. Trends Mach. Learn."},{"key":"211_CR7","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/s10958-008-9144-x","volume":"153","author":"EM Bronstein","year":"2008","unstructured":"Bronstein, E.M.: Approximation of convex sets by polytopes. J. Math. Sci. 153, 727\u2013762 (2008)","journal-title":"J. Math. Sci."},{"key":"211_CR8","doi-asserted-by":"crossref","unstructured":"Cameron, S.: Enhancing GJK: computing minimum and penetration distances between convex polyhedra. In: IEEE International Conference on Robotics and Automation, pp. 3112\u20133117 (2002)","DOI":"10.1109\/ROBOT.1997.606761"},{"key":"211_CR9","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/s10851-010-0251-1","volume":"40","author":"A Chambolle","year":"2012","unstructured":"Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40, 120\u2013145 (2012)","journal-title":"J. Math. Imaging Vis."},{"key":"211_CR10","doi-asserted-by":"publisher","first-page":"2783","DOI":"10.1137\/17M1134834","volume":"28","author":"A Chambolle","year":"2018","unstructured":"Chambolle, A., Ehrhardt, M.J., Richt\u00e1rik, P., Sch\u00f6nlieb, C.: Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging applications. SIAM J. Optim. 28, 2783\u20132808 (2018)","journal-title":"SIAM J. Optim."},{"key":"211_CR11","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-1-4419-9569-8_10","volume-title":"Fixed-Point Algorithms for Inverse Problems in Science and Engineering","author":"PL Combettes","year":"2011","unstructured":"Combettes, P.L., Pesquet, J.C.: Proximal splitting methods in signal processing. In: Bauschke, H.H., et al. (eds.) Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pp. 185\u2013212. Springer, Berlin (2011)"},{"key":"211_CR12","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/s10107-015-0946-6","volume":"158","author":"L Condat","year":"2016","unstructured":"Condat, L.: Fast projection onto the simplex and the $$\\ell _1$$ ball. Math. Program. 158, 575\u2013585 (2016)","journal-title":"Math. Program."},{"key":"211_CR13","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/j.laa.2006.03.022","volume":"416","author":"A Dax","year":"2006","unstructured":"Dax, A.: The distance between two convex sets. Linear Algebra Appl. 416, 184\u2013213 (2006)","journal-title":"Linear Algebra Appl."},{"key":"211_CR14","unstructured":"Eckstein, J.: Augmented Lagrangian and alternating direction methods for convex optimization: a tutorial and some illustrative computational results. RUTCOR Research Report, (2012)"},{"key":"211_CR15","unstructured":"Eckstein, J.: Splitting methods for monotone operators with applications to parallel optimization. Ph.D. Thesis, MIT (1989)"},{"key":"211_CR16","doi-asserted-by":"publisher","first-page":"1015","DOI":"10.1137\/09076934X","volume":"3","author":"E Esser","year":"2010","unstructured":"Esser, E., Zhang, X.Q., Chan, T.F.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3, 1015\u20131046 (2010)","journal-title":"SIAM J. Imaging Sci."},{"key":"211_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17283-0","volume-title":"CGAL Arrangements and Their Applications","author":"E Fogel","year":"2012","unstructured":"Fogel, E., Halperin, D., Wein, R.: CGAL Arrangements and Their Applications. Springer, Berlin (2012)"},{"key":"211_CR18","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0898-1221(76)90003-1","volume":"2","author":"D Gabay","year":"1976","unstructured":"Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximations. Comput. Math. Appl. 2, 17\u201340 (1976)","journal-title":"Comput. Math. Appl."},{"key":"211_CR19","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1137\/0304007","volume":"6","author":"E Gilbert","year":"1966","unstructured":"Gilbert, E.: An iterative procedure for computing the minimum of a quadratic form on a convex set. SIAM J. Control 6, 61\u201380 (1966)","journal-title":"SIAM J. Control"},{"key":"211_CR20","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1109\/70.88117","volume":"6","author":"E Gilbert","year":"1990","unstructured":"Gilbert, E., Foo, C.: Computing the distance between general convex objects in three-dimensional space. IEEE Trans. Robot. Autom. 6, 53\u201361 (1990)","journal-title":"IEEE Trans. Robot. Autom."},{"key":"211_CR21","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1109\/56.2083","volume":"4","author":"E Gilbert","year":"1988","unstructured":"Gilbert, E., Johnson, D., Keerthi, S.: A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE Trans. Robot. Autom. 4, 193\u2013203 (1988)","journal-title":"IEEE Trans. Robot. Autom."},{"key":"211_CR22","first-page":"59","volume":"34","author":"R Glowinski","year":"2014","unstructured":"Glowinski, R.: On alternating direction methods of multipliers: a historical perspective. Model. Simul. Optim. Sci. Technol. Comput. Methods Appl. Sci. 34, 59\u201382 (2014)","journal-title":"Model. Simul. Optim. Sci. Technol. Comput. Methods Appl. Sci."},{"key":"211_CR23","first-page":"41","volume":"2","author":"R Glowinski","year":"1975","unstructured":"Glowinski, R., Marrocco, A.: Sur l\u2019approximation par\u00e9l\u00e9ments finis d\u2019ordre unet lar\u00e9solution parp\u00e9nalisation-dualit\u00e9 d\u2019une classe deprobl\u00e8mes de Dirichlet non lin\u00e9aires. Revue Fr. Autom. Inform. Rech. Op\u00e9r., Anal. Num\u00e9r 2, 41\u201376 (1975)","journal-title":"Revue Fr. Autom. Inform. Rech. Op\u00e9r., Anal. Num\u00e9r"},{"key":"211_CR24","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1137\/100814494","volume":"5","author":"BS He","year":"2012","unstructured":"He, B.S., Yuan, X.M.: Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective. SIAM J. Imaging Sci. 5, 119\u2013149 (2012)","journal-title":"SIAM J. Imaging Sci."},{"key":"211_CR25","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1137\/110836936","volume":"50","author":"BS He","year":"2012","unstructured":"He, B.S., Yuan, X.M.: On the $$\\cal{O}(1\/n)$$ convergence rate of the Douglas\u2013Rachford alternating direction method. SIAM J. Numer. Anal. 50, 700\u2013709 (2012)","journal-title":"SIAM J. Numer. Anal."},{"key":"211_CR26","doi-asserted-by":"publisher","first-page":"2526","DOI":"10.1137\/140963467","volume":"7","author":"BS He","year":"2014","unstructured":"He, B.S., You, Y.F., Yuan, X.M.: On the convergence of primal-dual hybrid gradient algorithm. SIAM J. Imaging Sci. 7, 2526\u20132537 (2014)","journal-title":"SIAM J. Imaging Sci."},{"key":"211_CR27","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1109\/70.508439","volume":"12","author":"LE Kavraki","year":"1996","unstructured":"Kavraki, L.E., Svestka, P., Latombe, J.C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration space. IEEE Trans. Robot. Autom. 12, 566\u2013580 (1996)","journal-title":"IEEE Trans. Robot. Autom."},{"key":"211_CR28","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1137\/0214056","volume":"14","author":"JM Keil","year":"1985","unstructured":"Keil, J.M.: Decomposing a polygon into simpler components. SIAM J. Comput. 14, 799\u2013817 (1985)","journal-title":"SIAM J. Comput."},{"key":"211_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4022-9","volume-title":"Robot Motion Planning","author":"JC Latombe","year":"1991","unstructured":"Latombe, J.C.: Robot Motion Planning. Kluwer Academic Publishers, Boston (1991)"},{"key":"211_CR30","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1287\/moor.1070.0291","volume":"33","author":"AS Lewis","year":"2008","unstructured":"Lewis, A.S., Malick, J.: Alternating projections on manifolds. Math. Oper. Res. 33, 216\u2013234 (2008)","journal-title":"Math. Oper. Res."},{"key":"211_CR31","unstructured":"Lin, M., Canny, J.: A fast algorithm for incremental distance calculation. In: IEEE International Conference on Robotics and Automation, pp. 266\u2013275 (1991)"},{"key":"211_CR32","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s10589-009-9303-0","volume":"49","author":"Z Liu","year":"2011","unstructured":"Liu, Z., Fathi, Y.: An active index algorithm for the nearest point problem in a polyhedral cone. Comput. Optim. Appl. 49, 435\u2013456 (2011)","journal-title":"Comput. Optim. Appl."},{"key":"211_CR33","doi-asserted-by":"publisher","first-page":"774","DOI":"10.1016\/j.ejor.2014.04.003","volume":"238","author":"A Mayer","year":"2014","unstructured":"Mayer, A., Zelenyuk, V.: Aggregation of Malmquist productivity indexes allowing for realloction of resources. Eur. J. Oper. Res. 238, 774\u2013785 (2014)","journal-title":"Eur. J. Oper. Res."},{"key":"211_CR34","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1137\/0312003","volume":"12","author":"BF Mitchell","year":"1974","unstructured":"Mitchell, B.F., Dem\u2019Yanov, V.F., Malozemov, V.N.: Finding the point of a polyhedron closest to the origin. SIAM J. Control 12, 19\u201326 (1974)","journal-title":"SIAM J. Control"},{"key":"211_CR35","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.laa.2010.02.008","volume":"433","author":"A N\u00e9meth","year":"2010","unstructured":"N\u00e9meth, A., N\u00e9meth, S.: How to project onto an isotone projection cone. Linear Algebra Appl. 433, 41\u201351 (2010)","journal-title":"Linear Algebra Appl."},{"key":"211_CR36","first-page":"543","volume":"269","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method for unconstrained convex minimization problem with the rate of convergence $$O(1\/k^2)$$. Dokl. Akad. Nauk SSSR 269, 543\u2013547 (1983)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"211_CR37","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","volume":"103","author":"Y Nesterov","year":"2005","unstructured":"Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103, 127\u2013152 (2005)","journal-title":"Math. Program."},{"key":"211_CR38","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/s10107-018-1321-1","volume":"179","author":"D O\u2019Connor","year":"2020","unstructured":"O\u2019Connor, D., Vandenberghe, L.: On the equivalence of the primal-dual hybrid gradient method and Douglas\u2013Rachford splitting. Math. Program. 179, 85\u2013108 (2020)","journal-title":"Math. Program."},{"key":"211_CR39","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1109\/70.954768","volume":"17","author":"CJ Ong","year":"2001","unstructured":"Ong, C.J., Gilbert, E.: Fast versions of the Gilbert\u2013Johnson\u2013Keerthi distance algorithm: additional results and comparisons. IEEE Trans. Robot. Autom. 17, 531\u2013539 (2001)","journal-title":"IEEE Trans. Robot. Autom."},{"key":"211_CR40","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1007\/s10589-019-00124-7","volume":"74","author":"XL Qin","year":"2019","unstructured":"Qin, X.L., An, N.T.: Smoothing algorithms for computing the projection onto a Minkowski sum of convex sets. Comput. Optim. Appl. 74, 821\u2013850 (2019)","journal-title":"Comput. Optim. Appl."},{"key":"211_CR41","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1109\/3468.833102","volume":"30","author":"PL Rosin","year":"2000","unstructured":"Rosin, P.L.: Shape partitioning by convexity. IEEE Trans. Syst. Man, Cybern. A 30, 202\u2013210 (2000)","journal-title":"IEEE Trans. Syst. Man, Cybern. A"},{"key":"211_CR42","first-page":"3","volume":"15","author":"E Ryu","year":"2016","unstructured":"Ryu, E., Boyd, S.: A primer on monotone operator methods. Appl. Comput. Math. 15, 3\u201343 (2016)","journal-title":"Appl. Comput. Math."},{"key":"211_CR43","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF01582149","volume":"61","author":"K Sekitani","year":"1993","unstructured":"Sekitani, K., Yamamoto, Y.: Recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes. Math. Program. 61, 233\u2013249 (1993)","journal-title":"Math. Program."},{"key":"211_CR44","volume-title":"Image Analysis and Mathematical Morphology","author":"J Serra","year":"1983","unstructured":"Serra, J.: Image Analysis and Mathematical Morphology. Academic Press, Cambridge (1983)"},{"key":"211_CR45","volume-title":"CNC Programming Handbook","author":"P Smid","year":"2008","unstructured":"Smid, P.: CNC Programming Handbook. Industrial Press, New York (2008)"},{"key":"211_CR46","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF01586091","volume":"32","author":"JE Spingarn","year":"1985","unstructured":"Spingarn, J.E.: Applications of the method of partial inverses to convex programming: decomposition. Math. Program. 32, 199\u2013223 (1985)","journal-title":"Math. Program."},{"key":"211_CR47","doi-asserted-by":"crossref","unstructured":"Sra, S.: Fast projections onto $$\\ell _{1, q}$$-norm balls for grouped feature selection. In: Machine Learning and Knowledge Discovery in Databases, pp. 305\u2013317 (2011)","DOI":"10.1007\/978-3-642-23808-6_20"},{"key":"211_CR48","volume-title":"Structure and Interpretation of Classical Mechanics","author":"GJ Sussman","year":"2002","unstructured":"Sussman, G.J., Wisdom, J.: Structure and Interpretation of Classical Mechanics. MIT Press, Cambridge (2002)"},{"key":"211_CR49","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1137\/080714488","volume":"31","author":"E van den Berg","year":"2008","unstructured":"van den Berg, E., Friedlander, M.P.: Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31, 890\u2013912 (2008)","journal-title":"SIAM J. Sci. Comput."},{"key":"211_CR50","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/BF01580381","volume":"11","author":"P Wolfe","year":"1976","unstructured":"Wolfe, P.: Finding the nearest point in a polytope. Math. Program. 11, 128\u2013149 (1976)","journal-title":"Math. Program."},{"key":"211_CR51","doi-asserted-by":"publisher","first-page":"988","DOI":"10.1109\/TRO.2015.2451411","volume":"31","author":"Y Zheng","year":"2015","unstructured":"Zheng, Y., Yamane, K.: Generalized distance between compact convex sets: algorithms and applications. IEEE Trans. Robot. 31, 988\u20131003 (2015)","journal-title":"IEEE Trans. Robot."},{"key":"211_CR52","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1109\/TRA.2004.824682","volume":"20","author":"XY Zhu","year":"2004","unstructured":"Zhu, X.Y., Tso, S.K.: A peudodistance function and its applications. IEEE Trans. Robot. 20, 344\u2013352 (2004)","journal-title":"IEEE Trans. Robot."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-020-00211-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-020-00211-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-020-00211-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,10]],"date-time":"2024-08-10T00:25:19Z","timestamp":1723249519000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-020-00211-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,13]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["211"],"URL":"https:\/\/doi.org\/10.1007\/s10589-020-00211-0","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2020,7,13]]},"assertion":[{"value":"21 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 July 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}