{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T23:00:21Z","timestamp":1767913221053,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T00:00:00Z","timestamp":1596412800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T00:00:00Z","timestamp":1596412800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1566137"],"award-info":[{"award-number":["1566137"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1750780"],"award-info":[{"award-number":["1750780"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s00454-020-00224-w","type":"journal-article","created":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T15:10:42Z","timestamp":1596467442000},"page":"1244-1274","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Computing the Fr\u00e9chet Gap Distance"],"prefix":"10.1007","volume":"65","author":[{"given":"Chenglin","family":"Fan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6584-4843","authenticated-orcid":false,"given":"Benjamin","family":"Raichel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,8,3]]},"reference":[{"issue":"2","key":"224_CR1","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1137\/130920526","volume":"43","author":"PK Agarwal","year":"2014","unstructured":"Agarwal, P.K., Ben Avraham, R., Kaplan, H., Sharir, M.: Computing the discrete Fr\u00e9chet distance in subquadratic time. SIAM J. Comput. 43(2), 429\u2013449 (2014)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"224_CR2","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/s00454-009-9152-8","volume":"43","author":"H Alt","year":"2010","unstructured":"Alt, H., Buchin, M.: Can we compute the similarity between surfaces? Discrete Comput. Geom. 43(1), 78\u201399 (2010)","journal-title":"Discrete Comput. Geom."},{"key":"224_CR3","unstructured":"Alt, H., Efrat, A., Rote, G., Wenk, C.: Matching planar maps. In: 14th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore 2003), pp. 589\u2013598. ACM, New York (2003)"},{"issue":"1\u20132","key":"224_CR4","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1142\/S0218195995000064","volume":"5","author":"H Alt","year":"1995","unstructured":"Alt, H., Godau, M.: Computing the Fr\u00e9chet distance between two polygonal curves. Int. J. Comput. Geom. Appl. 5(1\u20132), 75\u201391 (1995)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"224_CR5","doi-asserted-by":"crossref","unstructured":"Alt, H., Knauer, Ch., Wenk, C.: Matching polygonal curves with respect to the Fr\u00e9chet distance. In: Annual Symposium on Theoretical Aspects of Computer Science (Dresden 2001). Lecture Notes in Comput. Sci., vol. 2010, pp. 63\u201374. Springer, Berlin (2001)","DOI":"10.1007\/3-540-44693-1_6"},{"key":"224_CR6","doi-asserted-by":"crossref","unstructured":"Ben Avraham, R., Filtser, O., Kaplan, H., Katz, M.J., Sharir, M.: The discrete and semicontinuous Fr\u00e9chet distance with shortcuts via approximate distance counting and selection. ACM Trans. Algorithms 11(4), #\u00a029 (2015)","DOI":"10.1145\/2700222"},{"key":"224_CR7","unstructured":"Ben Avraham, R., Kaplan, H., Sharir, M.: A faster algorithm for the discrete Fr\u00e9chet distance under translation (2015). arXiv:1501.03724"},{"issue":"9","key":"224_CR8","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"28","author":"JL Bentley","year":"1979","unstructured":"Bentley, J.L., Ottmann, T.A.: Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. 28(9), 643\u2013647 (1979)","journal-title":"IEEE Trans. Comput."},{"key":"224_CR9","unstructured":"Brakatsoulas, S., Pfoser, D., Salas, R., Wenk, C.: On map-matching vehicle tracking data. In: 31st VLDB Conference (Trondheim 2005), pp. 853\u2013864 (2005)"},{"key":"224_CR10","doi-asserted-by":"crossref","unstructured":"Bringmann, K.: Why walking the dog takes time: Fr\u00e9chet distance has no strongly subquadratic algorithms unless SETH fails. In: 55th Annual IEEE Symposium on Foundations of Computer Science (Philadelphia 2014), pp. 661\u2013670. IEEE Computer Soc., Los Alamitos (2014)","DOI":"10.1109\/FOCS.2014.76"},{"key":"224_CR11","doi-asserted-by":"crossref","unstructured":"Bringmann, K., K\u00fcnnemann, M., Nusser, A.: Fr\u00e9chet distance under translation: conditional hardness and an algorithm via offline dynamic grid reachability. In: 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2902\u20132921. SIAM, Philadelphia (2019)","DOI":"10.1137\/1.9781611975482.180"},{"issue":"3","key":"224_CR12","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1142\/S0218195911003652","volume":"21","author":"K Buchin","year":"2011","unstructured":"Buchin, K., Buchin, M., Gudmundsson, J., L\u00f6ffler, M., Luo, J.: Detecting commuting patterns by clustering subtrajectories. Int. J. Comput. Geom. Appl. 21(3), 253\u2013282 (2011)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"224_CR13","doi-asserted-by":"crossref","unstructured":"Buchin, K., Buchin, M., Meulemans, W., Mulzer, W.: Four Soviets walk the dog\u2014with an application to Alt\u2019s conjecture. In: 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1399\u20131413. ACM, New York (2014)","DOI":"10.1137\/1.9781611973402.103"},{"key":"224_CR14","doi-asserted-by":"crossref","unstructured":"Buchin, K., Buchin, M., Wenk, C.: Computing the Fr\u00e9chet distance between simple polygons in polynomial time. In: 22nd Annual Symposium on Computational Geometry, pp. 80\u201387. ACM, New York (2006)","DOI":"10.1145\/1137856.1137870"},{"key":"224_CR15","doi-asserted-by":"crossref","unstructured":"Buchin, M., Driemel, A., Speckmann, B.: Computing the Fr\u00e9chet distance with shortcuts is NP-hard. In: 30th Annual Symposium on Computational Geometry, pp. 367\u2013376. ACM, New York (2014)","DOI":"10.1145\/2582112.2582144"},{"issue":"5","key":"224_CR16","doi-asserted-by":"publisher","first-page":"1830","DOI":"10.1137\/120865112","volume":"42","author":"A Driemel","year":"2013","unstructured":"Driemel, A., Har-Peled, S.: Jaywalking your dog: computing the Fr\u00e9chet distance with shortcuts. SIAM J. Comput. 42(5), 1830\u20131866 (2013)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"224_CR17","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s00454-012-9402-z","volume":"48","author":"A Driemel","year":"2012","unstructured":"Driemel, A., Har-Peled, S., Wenk, C.: Approximating the Fr\u00e9chet distance for realistic curves in near linear time. Discrete Comput. Geom. 48(1), 94\u2013127 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"224_CR18","unstructured":"Eiter, T., Mannila, H.: Computing discrete Fr\u00e9chet distance. Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, CD-TR 94\/64 (1994)"},{"key":"224_CR19","unstructured":"Filtser, O., Katz, M.J.: The discrete Fr\u00e9chet gap (2015). arXiv:1506.04861"},{"key":"224_CR20","unstructured":"Filtser, O., Katz, M.J.: Algorithms for the discrete Fr\u00e9chet distance under translation. In: 16th Scandinavian Symposium and Workshops on Algorithm Theory. Leibniz Int. Proc. Inform., vol.\u00a0101, #\u00a020. Leibniz-Zent. Inform., Wadern (2018)"},{"key":"224_CR21","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Raichel, B.: The Fr\u00e9chet distance revisited and extended. ACM Trans. Algorithms 10(1), #\u00a03 (2014)","DOI":"10.1145\/2532646"},{"issue":"1","key":"224_CR22","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1142\/S0219720008003278","volume":"6","author":"M Jiang","year":"2008","unstructured":"Jiang, M., Xu, Y., Zhu, B.: Protein structure-structure alignment with discrete Fr\u00e9chet distance. J. Bioinform. Comput. Biol. 6(1), 51\u201364 (2008)","journal-title":"J. Bioinform. Comput. Biol."},{"key":"224_CR23","doi-asserted-by":"crossref","unstructured":"Kim, M.-S., Kim, S.-W., Shin, M.: Optimization of subsequence matching under time warping in time-series databases. In: ACM Symposium on Applied Computing (Santa Fe 2005), pp. 581\u2013586. ACM, New York (2005)","DOI":"10.1145\/1066677.1066814"},{"issue":"3","key":"224_CR24","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/j.comgeo.2005.01.004","volume":"37","author":"G Rote","year":"2007","unstructured":"Rote, G.: Computing the Fr\u00e9chet distance between piecewise smooth curves. Comput. Geom. 37(3), 162\u2013174 (2007)","journal-title":"Comput. Geom."},{"issue":"6","key":"224_CR25","doi-asserted-by":"publisher","first-page":"1138","DOI":"10.1109\/TASL.2008.924595","volume":"16","author":"J Serr\u00e0","year":"2008","unstructured":"Serr\u00e0, J., G\u00f3mez, E., Herrera, P., Serra, X.: Chroma binary similarity and local alignment applied to cover song identification. IEEE Trans. Audio Speech Language Process. 16(6), 1138\u20131151 (2008)","journal-title":"IEEE Trans. Audio Speech Language Process."},{"key":"224_CR26","unstructured":"Wenk, C., Salas, R., Pfoser, D.: Addressing the need for map-matching speed: Localizing global curve-matching algorithms. In: 18th International Conference on Scientific and Statistical Database Management (Vienna 2006), pp. 879\u2013888. IEEE Computer Soc., Los Alamitos (2006)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00224-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-020-00224-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00224-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,2]],"date-time":"2021-08-02T23:17:09Z","timestamp":1627946229000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-020-00224-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,3]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["224"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00224-w","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,3]]},"assertion":[{"value":"4 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 May 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}