{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:47:02Z","timestamp":1740109622876,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,11,5]],"date-time":"2015-11-05T00:00:00Z","timestamp":1446681600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,11,5]],"date-time":"2015-11-05T00:00:00Z","timestamp":1446681600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["CCF 1423230"],"award-info":[{"award-number":["CCF 1423230"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["CAREER 1453472"],"award-info":[{"award-number":["CAREER 1453472"]}],"id":[{"id":"10.13039\/100000083","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":[[2016,1]]},"DOI":"10.1007\/s00454-015-9737-3","type":"journal-article","created":{"date-parts":[[2015,11,5]],"date-time":"2015-11-05T14:24:14Z","timestamp":1446733454000},"page":"39-73","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["How to Walk Your Dog in the Mountains with No Magic Leash"],"prefix":"10.1007","volume":"55","author":[{"given":"Sariel","family":"Har-Peled","sequence":"first","affiliation":[]},{"given":"Amir","family":"Nayyeri","sequence":"additional","affiliation":[]},{"given":"Mohammad","family":"Salavatipour","sequence":"additional","affiliation":[]},{"given":"Anastasios","family":"Sidiropoulos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,11,5]]},"reference":[{"key":"9737_CR1","first-page":"1679","volume":"26","author":"PK Agarwal","year":"1997","unstructured":"Agarwal, P.K., Aronov, B., O\u2019Rourke, J., Schevon, C.A.: Star unfolding of a polytope with applications. SIAM J. Comput. 26, 1679\u20131713 (1997)","journal-title":"SIAM J. Comput."},{"key":"9737_CR2","unstructured":"Alt, H., Buchin, M.: Semi-computability of the Fr\u00e9chet distance between surfaces. In: Proceedings of the 21st European Workshop on Computational Geometry, pp. 45\u201348 (2005)"},{"key":"9737_CR3","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, 75\u201391 (1995)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9737_CR4","doi-asserted-by":"crossref","unstructured":"Bennis, C., V\u00e9zien, J.-M., Igl\u00e9sias, G., Gagalowicz, A.: Piecewise surface flattening for non-distorted texture mapping. In: Sederberg, T.W. (ed). Proceedings of SIGGRAPH \u201991, vol. 25, pp. 237\u2013246. ACM, New York (1991)","DOI":"10.1145\/127719.122744"},{"key":"9737_CR5","unstructured":"Brakatsoulas, S., Pfoser, D., Salas, R., Wenk, C.: On map-matching vehicle tracking data. In: Proceedings of 31st VLDB Conference, VLDB Endowment, pp. 853\u2013864. Norwegian University of Science & Technology, Trondheim (2005)"},{"issue":"3","key":"9737_CR6","doi-asserted-by":"publisher","first-page":"1149","DOI":"10.1137\/07069078X","volume":"23","author":"GA Brightwell","year":"2009","unstructured":"Brightwell, G.A., Winkler, P.: Submodular percolation. SIAM J. Discrete Math. 23(3), 1149\u20131178 (2009)","journal-title":"SIAM J. Discrete Math."},{"key":"9737_CR7","doi-asserted-by":"crossref","unstructured":"Buchin, K., Buchin, M., Gudmundsson, J.: Detecting single file movement. In: Proceedings of 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS), pp. 288\u2013297. ACM, New York (2008)","DOI":"10.1145\/1463434.1463476"},{"key":"9737_CR8","doi-asserted-by":"crossref","unstructured":"Buchin, K., Buchin, M., Gudmundsson, J., Maarten, L., Luo, J.: Detecting commuting patterns by clustering subtrajectories. In: Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC), pp. 644\u2013655. Springer, Heidelberg (2008)","DOI":"10.1007\/978-3-540-92182-0_57"},{"key":"9737_CR9","doi-asserted-by":"crossref","unstructured":"Buchin, M., Driemel, A., Speckmann, B.: Computing the Fr\u00e9chet distance with shortcuts is NP-hard. In: Proceedings of the 30th Annual Symposium on Computational Geometry SOCG\u201914 (Kyoto, Japan), pp. 367\u2013376. ACM, New York, NY (2014)","DOI":"10.1145\/2582112.2582144"},{"key":"9737_CR10","unstructured":"Chambers, E.W., Letscher, D.: On the height of a homotopy. In: Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG), pp. 14. University of British Columbia, Vancouver (2009)"},{"key":"9737_CR11","unstructured":"Chambers, E.W., Letscher, D.: Erratum for on the height of a homotopy. \n                    http:\/\/mathcs.slu.edu\/~chambers\/papers\/hherratum.pdf\n                    \n                   (2010)"},{"key":"9737_CR12","unstructured":"Chambers, G.R., Rotman, R.: Contracting loops on a Riemannian 2-surface (2013). \n                    arXiv:1311.2995"},{"key":"9737_CR13","doi-asserted-by":"crossref","unstructured":"Chambers, E.W., Wang, Y.: Measuring similarity between curves on 2-manifolds via homotopy area. In: Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG), pp. 425\u2013434. ACM, New York (2013)","DOI":"10.1145\/2462356.2462375"},{"issue":"3","key":"9737_CR14","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/j.comgeo.2009.02.008","volume":"43","author":"EW Chambers","year":"2010","unstructured":"Chambers, E.W., Colin de Verdi\u00e8re, E., Erickson, J., Lazard, S., Lazarus, F., Thite, S.: Homotopic Fr\u00e9chet distance between curves or, walking your dog in the woods in polynomial time. Comput. Geom. Theory Appl. 43(3), 295\u2013311 (2010)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9737_CR15","unstructured":"Chambers, E.W., Letscher, D., Ju, T., Liu, L.: Isotopic Fr\u00e9chet distance. In: Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG), pp. 229\u2013234. CCCG, Toronto (2011)"},{"key":"9737_CR16","first-page":"9:1","volume":"7","author":"AF Cook","year":"2010","unstructured":"Cook, A.F., Wenk, C.: Geodesic Fr\u00e9chet distance inside a simple polygon. ACM Trans. Algorithms 7, 9:1\u20139:19 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"9737_CR17","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/s00453-012-9723-6","volume":"69","author":"AF Cook","year":"2014","unstructured":"Cook, A.F., Wenk, C.: Shortest path problems on a polyhedral surface. Algorithmica 69(1), 58\u201377 (2014)","journal-title":"Algorithmica"},{"key":"9737_CR18","doi-asserted-by":"crossref","unstructured":"Cook, A.F., Driemel, A., Har-Peled, S., Sherette, J., Wenk, C.: Computing the Fr\u00e9chet distance between folded polygons. In: Proceedings of the 12th Workshop Algorithms Data Structure (WADS), pp. 267\u2013278. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-22300-6_23"},{"key":"9737_CR19","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, 94\u2013127 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"9737_CR20","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s00454-002-2886-1","volume":"28","author":"A Efrat","year":"2002","unstructured":"Efrat, A., Guibas, L.J., Har-Peled, S., Mitchell, J.S.B., Murali, T.M.: New similarity measures between polylines with applications to morphing and polygon sweeping. Discrete Comput. Geom. 28, 535\u2013569 (2002)","journal-title":"Discrete Comput. Geom."},{"key":"9737_CR21","unstructured":"Eiter, T., Mannila, H.: Computing discrete Fr\u00e9chet distance. Technical Report CD-TR 94\/64, Christian Doppler Laboratory for Expert Systems, TU, Vienna (1994)"},{"issue":"4","key":"9737_CR22","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0167-8396(96)00031-3","volume":"14","author":"MS Floater","year":"1997","unstructured":"Floater, M.S.: Parameterization and smooth approximation of surface triangulations. Comput. Aided Geom. Des. 14(4), 231\u2013250 (1997)","journal-title":"Comput. Aided Geom. Des."},{"key":"9737_CR23","first-page":"4","volume":"3","author":"M Frech\u00e9t","year":"1924","unstructured":"Frech\u00e9t, M.: Sur la distance de deux surfaces. Ann. Soc. Polonaise Math. 3, 4\u201319 (1924)","journal-title":"Ann. Soc. Polonaise Math."},{"key":"9737_CR24","unstructured":"Godau, M.: On the complexity of measuring the similarity between geometric objects in higher dimensions. PhD Thesis, Free University of Berlin (1999)"},{"key":"9737_CR25","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Raichel, B.: The Fr\u00e9chet distance revisited and extended. In: Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG), pp. 448\u2013457. ACM Press, New York (2011)","DOI":"10.1145\/1998196.1998269"},{"key":"9737_CR26","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Nayyeri, A., Salavatipour, M., Sidiropoulos, A.: How to walk your dog in the mountains with no magic leash. In: Proceedings of the 28th Annual ACM Symposium on Computational Geometry (SoCG), pp. 121\u2013130. ACM, New York (2012)","DOI":"10.1145\/2261250.2261269"},{"key":"9737_CR27","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"MR Henzinger","year":"1997","unstructured":"Henzinger, M.R., Klein, P., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55, 3\u201323 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"9737_CR28","doi-asserted-by":"crossref","unstructured":"Keogh, E.J., Pazzani, M.J.: Scaling up dynamic time warping to massive dataset. In: Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery, pp. 1\u201311. Springer, Prague (1999)","DOI":"10.1007\/978-3-540-48247-5_1"},{"key":"9737_CR29","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: Proceedings of the ACM Symposium on Applied Computing, pp. 581\u2013586. ACM, New York (2005)","DOI":"10.1145\/1066677.1066814"},{"key":"9737_CR30","doi-asserted-by":"crossref","unstructured":"Lewis, P.M., II, Stearns, R.E., Hartmanis, J.: Memory bounds for recognition of context-free and context-sensitive languages. In: Proceedings of the 6th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 191\u2013202. ACM, New York (1965)","DOI":"10.1109\/FOCS.1965.14"},{"key":"9737_CR31","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"9737_CR32","doi-asserted-by":"crossref","unstructured":"Mascret, A., Devogele, T., Le Berre, I., H\u00e9naff, A.: Coastline matching process based on the discrete Fr\u00e9chet distance. In: Proceedings of the 12th International Symposium on Spatial Data Handling, pp. 383\u2013400. Springer, Berlin (2006)","DOI":"10.1007\/3-540-35589-8_25"},{"key":"9737_CR33","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1137\/0216045","volume":"16","author":"JSB Mitchell","year":"1987","unstructured":"Mitchell, J.S.B., Mount, D.M., Papadimitriou, C.H.: The discrete geodesic problem. SIAM J. Comput. 16, 647\u2013668 (1987)","journal-title":"SIAM J. Comput."},{"key":"9737_CR34","unstructured":"Papasoglu, P.: Contracting thin disks (2013). \n                    arXiv:1309.2967"},{"key":"9737_CR35","doi-asserted-by":"crossref","unstructured":"Piponi, D., Borshukov, G.: Seamless texture mapping of subdivision surfaces by model pelting and texture blending. In: Proceedings of the SIGGRAPH 2000, pp. 471\u2013478. ACM, New York (2000)","DOI":"10.1145\/344779.344990"},{"issue":"6","key":"9737_CR36","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 Lang. Process. 16(6), 1138\u20131151 (2008)","journal-title":"IEEE Trans. Audio Speech Lang. Process."},{"key":"9737_CR37","unstructured":"Sheffer, A., de\u00a0Sturler, E.: Surface parameterization for meshing by triangulation flattening. In: Proceedings of the 9th International Meshing Roundtable, pp. 161\u2013172. Springer, Berlin (2000)"},{"key":"9737_CR38","unstructured":"Sherette, J., Wenk, C.: Simple curve embedding. CoRR (2013). \n                    arXiv:1303.0821"},{"key":"9737_CR39","unstructured":"Wenk, C., Salas, R., Pfoser, D.: Addressing the need for map-matching speed: Localizing global curve-matching algorithms. In: Proceedings of the 18th Conference on Scientific and Statistical Database Management, pp. 879\u2013888. Springer, Berlin (2006)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9737-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-015-9737-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9737-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9737-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:32:13Z","timestamp":1589697133000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-015-9737-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,5]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9737"],"URL":"https:\/\/doi.org\/10.1007\/s00454-015-9737-3","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2015,11,5]]},"assertion":[{"value":"26 January 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 September 2015","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 September 2015","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2015","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}