{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,29]],"date-time":"2026-08-29T16:09:05Z","timestamp":1788019745672,"version":"build-2784847793"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>\n            Given two simplicial complexes in R\n            <jats:sup>d<\/jats:sup>\n            and start and end vertices in each complex, we show how to compute curves (in each complex) between these vertices, such that the weak Fr\u00e9chet distance between these curves is minimized. As a polygonal curve is a complex, this generalizes the regular notion of weak Fr\u00e9chet distance between curves. We also generalize the algorithm to handle an input of\n            <jats:italic>k<\/jats:italic>\n            simplicial complexes.\n          <\/jats:p>\n          <jats:p>\n            Using this new algorithm, we can solve a slew of new problems, from computing a mean curve for a given collection of curves to various motion planning problems. Additionally, we show that for the mean curve problem, when the\n            <jats:italic>k<\/jats:italic>\n            input curves are\n            <jats:italic>c<\/jats:italic>\n            -packed, one can (1+\u03b5-approximate the mean curve in near-linear time, for fixed\n            <jats:italic>k<\/jats:italic>\n            and \u03b5.\n          <\/jats:p>\n          <jats:p>Additionally, we present an algorithm for computing the strong Fr\u00e9chet distance between two curves, which is simpler than previous algorithms and avoids using parametric search.<\/jats:p>","DOI":"10.1145\/2532646","type":"journal-article","created":{"date-parts":[[2014,2,25]],"date-time":"2014-02-25T13:20:45Z","timestamp":1393334445000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":44,"title":["The fr\u00e9chet distance revisited and extended"],"prefix":"10.1145","volume":"10","author":[{"given":"Sariel","family":"Har-Peled","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, IL, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benjamin","family":"Raichel","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, IL, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9466-1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9152-8"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00085-3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000064"},{"key":"e_1_2_1_5_1","volume-title":"Proc. 31st VLDB Conference. 853--864","author":"Brakatsoulas S.","unstructured":"S. Brakatsoulas , D. Pfoser , R. Salas , and C. Wenk . 2005. On map-matching vehicle tracking data . In Proc. 31st VLDB Conference. 853--864 . S. Brakatsoulas, D. Pfoser, R. Salas, and C. Wenk. 2005. On map-matching vehicle tracking data. In Proc. 31st VLDB Conference. 853--864."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1463434.1463476"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92182-0_57"},{"key":"e_1_2_1_8_1","volume-title":"23rd Euro. Workshop on Comput. Geom. 170--173","author":"Buchin K.","unstructured":"K. Buchin , M. Buchin , C. Knauer , G. Rote , and C. Wenk . 2007. How difficult is it to walk the dog&quest; In Proc . 23rd Euro. Workshop on Comput. Geom. 170--173 . K. Buchin, M. Buchin, C. Knauer, G. Rote, and C. Wenk. 2007. How difficult is it to walk the dog&quest; In Proc. 23rd Euro. Workshop on Comput. Geom. 170--173."},{"key":"e_1_2_1_9_1","volume-title":"Proc. 18th Ann. European Symp. Algorithms. 63--74","author":"Buchin K.","unstructured":"K. Buchin , M. Buchin , and A. Schulz . 2010a. Fr\u00e9chet distance of surfaces: Some simple hard cases . In Proc. 18th Ann. European Symp. Algorithms. 63--74 . K. Buchin, M. Buchin, and A. Schulz. 2010a. Fr\u00e9chet distance of surfaces: Some simple hard cases. In Proc. 18th Ann. European Symp. Algorithms. 63--74."},{"key":"e_1_2_1_10_1","volume-title":"Proc. 18th Ann. European Symp. on Algorithms (ESA).","volume":"6346","author":"Buchin K.","unstructured":"K. Buchin , M. Buchin , M. van Kreveld , M. Lffler , R. I. Silveira , C. Wenk , and L. Wiratma . 2010b. Median trajectories . In Proc. 18th Ann. European Symp. on Algorithms (ESA). Vol. 6346 . Springer, 463--474. K. Buchin, M. Buchin, M. van Kreveld, M. Lffler, R. I. Silveira, C. Wenk, and L. Wiratma. 2010b. Median trajectories. In Proc. 18th Ann. European Symp. on Algorithms (ESA). Vol. 6346. Springer, 463--474."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868247"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810959.1811019"},{"key":"e_1_2_1_13_1","volume-title":"Proc. 16th Canad. Conf. Comput. Geom. 162--165","author":"Dumitrescu A.","unstructured":"A. Dumitrescu and G. Rote . 2004. On the Fr\u00e9chet distance of a set of curves . In Proc. 16th Canad. Conf. Comput. Geom. 162--165 . A. Dumitrescu and G. Rote. 2004. On the Fr\u00e9chet distance of a set of curves. In Proc. 16th Canad. Conf. Comput. Geom. 162--165."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998269"},{"key":"e_1_2_1_16_1","volume-title":"Proc. of the 3rd Euro. Conf. Princip. Data Mining and Know. Disc. 1--11","author":"Keogh E. J.","unstructured":"E. J. Keogh and M. J. Pazzani . 1999. Scaling up dynamic time warping to massive dataset . In Proc. of the 3rd Euro. Conf. Princip. Data Mining and Know. Disc. 1--11 . E. J. Keogh and M. J. Pazzani. 1999. Scaling up dynamic time warping to massive dataset. In Proc. of the 3rd Euro. Conf. Princip. Data Mining and Know. Disc. 1--11."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066677.1066814"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001498000348"},{"key":"e_1_2_1_19_1","volume-title":"Proc. 9th Ann. European Symp. Algorithms. 518--529","author":"Maheshwari A.","unstructured":"A. Maheshwari , J.-R. Sack , K. Shabaz , and H. Zarrabi-Zadeh . 2011. Improved algorithms for partial curve matching . In Proc. 9th Ann. European Symp. Algorithms. 518--529 . A. Maheshwari, J.-R. Sack, K. Shabaz, and H. Zarrabi-Zadeh. 2011. Improved algorithms for partial curve matching. In Proc. 9th Ann. European Symp. Algorithms. 518--529."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90177-J"},{"key":"e_1_2_1_21_1","volume-title":"Proc. 7th Int. Conf. Comp. Vision. 108--115","author":"Munich M. E.","unstructured":"M. E. Munich and P. Perona . 1999. Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification . In Proc. 7th Int. Conf. Comp. Vision. 108--115 . M. E. Munich and P. Perona. 1999. Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification. In Proc. 7th Int. Conf. Comp. Vision. 108--115."},{"key":"e_1_2_1_22_1","volume-title":"Proc. 9th Int. Conf. Doc. Analy. Recog. 461--465","author":"Sriraghavendra E.","unstructured":"E. Sriraghavendra , K. Karthik , and C. Bhattacharyya . 2007. Fr\u00e9chet distance based approach for searching online handwritten documents . In Proc. 9th Int. Conf. Doc. Analy. Recog. 461--465 . E. Sriraghavendra, K. Karthik, and C. Bhattacharyya. 2007. Fr\u00e9chet distance based approach for searching online handwritten documents. In Proc. 9th Int. Conf. Doc. Analy. Recog. 461--465."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.006"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDBM.2006.11"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2532646","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2532646","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:05Z","timestamp":1750278125000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2532646"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1145\/2532646"],"URL":"https:\/\/doi.org\/10.1145\/2532646","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"2012-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}