{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:33:25Z","timestamp":1760150005083,"version":"build-2065373602"},"reference-count":44,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T00:00:00Z","timestamp":1696550400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100007197","name":"USPHS","doi-asserted-by":"publisher","award":["GM53275","HG006139"],"award-info":[{"award-number":["GM53275","HG006139"]}],"id":[{"id":"10.13039\/100007197","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The Hausdorff distance between two closed sets has important theoretical and practical applications. Yet apart from finite point clouds, there appear to be no generic algorithms for computing this quantity. Because many infinite sets are defined by algebraic equalities and inequalities, this a huge gap. The current paper constructs Frank\u2013Wolfe and projected gradient ascent algorithms for computing the Hausdorff distance between two compact convex sets. Although these algorithms are guaranteed to go uphill, they can become trapped by local maxima. To avoid this defect, we investigate a homotopy method that gradually deforms two balls into the two target sets. The Frank\u2013Wolfe and projected gradient algorithms are tested on two pairs (A,B) of compact convex sets, where: (1) A is the box [\u22121,1] translated by 1 and B is the intersection of the unit ball and the non-negative orthant; and (2) A is the probability simplex and B is the \u21131 unit ball translated by 1. For problem (2), we find the Hausdorff distance analytically. Projected gradient ascent is more reliable than the Frank\u2013Wolfe algorithm and finds the exact solution of problem (2). Homotopy improves the performance of both algorithms when the exact solution is unknown or unattained.<\/jats:p>","DOI":"10.3390\/a16100471","type":"journal-article","created":{"date-parts":[[2023,10,9]],"date-time":"2023-10-09T04:52:36Z","timestamp":1696827156000},"page":"471","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Computation of the Hausdorff Distance between Two Compact Convex Sets"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1313-5030","authenticated-orcid":false,"given":"Kenneth","family":"Lange","sequence":"first","affiliation":[{"name":"Department of Computational Medicine, University of California, Los Angeles, CA 90095, USA"},{"name":"Department of Human Genetics, University of California, Los Angeles, CA 90095, USA"},{"name":"Department of Statistics, University of California, Los Angeles, CA 90095, USA"}]}],"member":"1968","published-online":{"date-parts":[[2023,10,6]]},"reference":[{"key":"ref_1","unstructured":"Aubin, J.-P. (1977). Applied Abstract Analysis, Wiley."},{"key":"ref_2","unstructured":"Munkres, J. (1999). Topology, Prentice Hall. [2nd ed.]."},{"key":"ref_3","first-page":"1","article-title":"Distance between sets: A survey","volume":"26","author":"Conci","year":"2017","journal-title":"Adv. Math. Sci. Appl."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1137\/19M1307299","article-title":"Optimal control of soft materials using a Hausdorff distance functional","volume":"59","author":"Ortigosa","year":"2021","journal-title":"SIAM J. Control. Optim."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1070\/RM1969v024n05ABEH001359","article-title":"Some questions of the theory of approximations of functions and sets in the Hausdorff metric","volume":"24","author":"Sendov","year":"1969","journal-title":"Russ. Math. Surv."},{"key":"ref_6","unstructured":"Cornean, H.D., and Purice, R. (2012). Spectral Analysis of Quantum Hamiltonians: Spectral Days 2010, Springer."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"4099","DOI":"10.1007\/s11042-019-07774-z","article-title":"Object recognition using Hausdorff distance for multimedia applications","volume":"79","author":"Kumar","year":"2020","journal-title":"Multimed. Tools Appl."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1109\/34.232073","article-title":"Comparing images using the Hausdorff distance","volume":"15","author":"Huttenlocher","year":"1993","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"381","DOI":"10.3233\/ICA-2012-0413","article-title":"Enhancing a disparity map by color segmentation","volume":"19","author":"Lertchuwongsa","year":"2012","journal-title":"Integr.-Comput.-Aided Eng."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1111\/j.1749-6632.1987.tb48732.x","article-title":"Fractal modeling of biological structures","volume":"504","author":"Barnsley","year":"1987","journal-title":"Ann. N. Y. Acad. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"215","DOI":"10.3934\/dcdsb.2005.5.215","article-title":"Approximation of attractors of nonautonomous dynamical systems","volume":"5","author":"Aulbach","year":"2005","journal-title":"Discret. Contin. Dyn. Syst. Ser. B"},{"key":"ref_12","unstructured":"Dubuisson, M.-P., and Jain, A.K. (1994, January 9\u201313). A modified Hausdorff distance for object matching. Proceedings of the 12th International Conference on Pattern Recognition, Jerusalem, Israel."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"833","DOI":"10.4134\/CKMS.2013.28.4.833","article-title":"Computing the Hausdorff distance between two sets of parametric curves","volume":"28","author":"Kim","year":"2013","journal-title":"Commun. Korean Math. Soc."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0020-0190(91)90233-8","article-title":"Computing the minimum Hausdorff distance between two point sets on a line under translation","volume":"38","author":"Rote","year":"1991","journal-title":"Inf. Process. Lett."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"2153","DOI":"10.1109\/TPAMI.2015.2408351","article-title":"An efficient algorithm for calculating the exact Hausdorff distance","volume":"37","author":"Taha","year":"2015","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"261","DOI":"10.3233\/ICA-170544","article-title":"An efficient approach to directly compute the exact Hausdorff distance for 3D point sets","volume":"24","author":"Zhang","year":"2017","journal-title":"Integr. Comput.-Aided Eng."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0020-0190(83)90042-X","article-title":"A linear time algorithm for the Hausdorff distance between convex polygons","volume":"17","author":"Atallah","year":"1983","journal-title":"Inf. Process. Lett."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0020-0190(97)00140-3","article-title":"Calculating the Hausdorff distance between curves","volume":"64","author":"Belogay","year":"1997","journal-title":"Inf. Process. Lett."},{"key":"ref_19","unstructured":"Elber, G., and Grandine, T. (2008, January 23\u201325). Hausdorff and minimal distances between parametric freeforms in R2 and R3. Proceedings of the International Conference on Geometric Modeling and Processing, Hangzhou, China."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Bauschke, H.H., and Combettes, P.L. (2017). Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer.","DOI":"10.1007\/978-3-319-48311-5"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Beck, A. (2017). First-Order Methods in Optimization, SIAM.","DOI":"10.1137\/1.9781611974997"},{"key":"ref_22","first-page":"2384","article-title":"Proximal distance algorithms: Theory and practice","volume":"20","author":"Keys","year":"2019","journal-title":"J. Mach. Learn. Res."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Lange, K. (2016). MM Optimization Algorithms, SIAM.","DOI":"10.1137\/1.9781611974409"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/BF01898615","article-title":"Minimalstellen von funktionen und extremalpunkte","volume":"9","author":"Bauer","year":"1958","journal-title":"Arch. Math."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Clarke, F. (2013). Functional Analysis, Calculus of Variations and Optimal Control, Springer.","DOI":"10.1007\/978-1-4471-4820-3"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1002\/nav.3800030109","article-title":"An algorithm for quadratic programming","volume":"3","author":"Frank","year":"1956","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_27","unstructured":"Jaggi, M. (2013, January 17\u201319). Revisiting Frank-Wolfe: Projection-free sparse convex optimization. Proceedings of the International Conference on Machine Learning, PMLR, Atlanta, Georgia."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1561\/2400000003","article-title":"Proximal algorithms","volume":"1","author":"Parikh","year":"2014","journal-title":"Found. Trends Optim."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1111\/j.1467-9469.2009.00681.x","article-title":"On the bumpy road to the dominant mode","volume":"37","author":"Zhou","year":"2009","journal-title":"Scand. J. Stat."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1198\/0003130042836","article-title":"A tutorial on MM algorithms","volume":"58","author":"Hunter","year":"2004","journal-title":"Am. Stat."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"McLachlan, G.J., and Krishnan, T. (2008). The EM Algorithm and Extensions, Wiley. [2nd ed.].","DOI":"10.1002\/9780470191613"},{"key":"ref_32","first-page":"247","article-title":"The Hausdorff distance between some sets of points","volume":"23","year":"2018","journal-title":"Math. Commun."},{"key":"ref_33","unstructured":"Won, J.-H., Zu, J., and Lange, K. (2019, January 9\u201315). Projection onto Minkowski sums with application to constrained learning. Proceedings of the 36th International Conference on Machine Learning 2019, Long Beach, CA, USA."},{"key":"ref_34","unstructured":"Garber, D., and Hazan, E. (2015, January 7\u20139). Faster rates for the Frank-Wolfe method over strongly-convex sets. Proceedings of the International Conference on Machine Learning, PMLR, Lille, France."},{"key":"ref_35","first-page":"52","article-title":"On strongly E-convex sets and strongly E-convex cone sets","volume":"11","author":"Majeed","year":"2019","journal-title":"J. AL-Qadisiyah Comput. Sci. Math."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Beck, A. (2014). Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB, SIAM.","DOI":"10.1137\/1.9781611973655"},{"key":"ref_37","unstructured":"Bertsekas, D.P. (1999). Nonlinear Programming, Athena Scientific. [2nd ed.]."},{"key":"ref_38","unstructured":"Lacoste-Julien, S. (2016). Convergence rate of Frank-Wolfe for non-convex objectives. arXiv."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Lange, K. (2023). Closest Farthest Widest, unpublished.","DOI":"10.3390\/a17030095"},{"key":"ref_40","unstructured":"Lange, K., Won, J.-H., Landeros, A., and Zhou, H. (2020). Wiley StatsRef: Statistics Reference Online, Wiley Online Library."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1016\/j.cagd.2010.04.004","article-title":"Precise Hausdorff distance computation between polygonal meshes","volume":"27","author":"Hanniel","year":"2010","journal-title":"Comput. Aided Geom. Des."},{"key":"ref_42","first-page":"41","article-title":"Fast and accurate Hausdorff distance calculation between meshes","volume":"13","author":"Guthe","year":"2005","journal-title":"J. WSCG"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Lin, M.C., and Manocha, D. (1996). Applied Computational Geometry towards Geometric Engineering, Springer.","DOI":"10.1007\/BFb0014474"},{"key":"ref_44","unstructured":"Aspert, N., Santa-Cruz, D., and Ebrahimi, T. (2002, January 26\u201329). Mesh: Measuring errors between surfaces using the Hausdorff distance. Proceedings of the IEEE International Conference on Multimedia and Expo, Lausanne, Switzerland."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/10\/471\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:02:07Z","timestamp":1760130127000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/10\/471"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,6]]},"references-count":44,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2023,10]]}},"alternative-id":["a16100471"],"URL":"https:\/\/doi.org\/10.3390\/a16100471","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2023,10,6]]}}}