{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:24Z","timestamp":1750694724584},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662489703"},{"type":"electronic","value":"9783662489710"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48971-0_44","type":"book-chapter","created":{"date-parts":[[2015,11,25]],"date-time":"2015-11-25T23:00:57Z","timestamp":1448492457000},"page":"517-528","source":"Crossref","is-referenced-by-count":2,"title":["Improved Approximation for Fr\u00e9chet Distance on c-packed Curves Matching Conditional Lower Bounds"],"prefix":"10.1007","author":[{"given":"Karl","family":"Bringmann","sequence":"first","affiliation":[]},{"given":"Marvin","family":"K\u00fcnnemann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,11,27]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Agarwal, P., Avraham, R.B., Kaplan, H., Sharir, M.: Computing the discrete Fr\u00e9chet distance in subquadratic time. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 156\u2013167 (2013)","key":"44_CR1","DOI":"10.1137\/1.9781611973105.12"},{"issue":"1\u20132","key":"44_CR2","first-page":"78","volume":"5","author":"H Alt","year":"1995","unstructured":"Alt, H., Godau, M.: Computing the Fr\u00e9chet distance between two polygonal curves. Internat. J. Comput. Geom. Appl. 5(1\u20132), 78\u201399 (1995)","journal-title":"Internat. J. Comput. Geom. Appl."},{"issue":"1","key":"44_CR3","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s00453-003-1042-5","volume":"38","author":"H Alt","year":"2004","unstructured":"Alt, H., Knauer, C., Wenk, C.: Comparison of distance measures for planar curves. Algorithmica 38(1), 45\u201358 (2004)","journal-title":"Algorithmica"},{"key":"44_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/11841036_8","volume-title":"Algorithms \u2013 ESA 2006","author":"B Aronov","year":"2006","unstructured":"Aronov, B., Har-Peled, S., Knauer, C., Wang, Y., Wenk, C.: Fr\u00e9chet distance for curves, revisited. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 52\u201363. Springer, Heidelberg (2006)"},{"unstructured":"Brakatsoulas, S., Pfoser, D., Salas, R., Wenk, C.: On map-matching vehicle tracking data. In: Proceedings of the 31st International Conference on Very Large Data Bases (VLDB 2005), pp. 853\u2013864 (2005)","key":"44_CR5"},{"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: Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014), pp. 661\u2013670 (2014)","key":"44_CR6","DOI":"10.1109\/FOCS.2014.76"},{"issue":"3","key":"44_CR7","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. Internat. J. Comput. Geom. Appl. 21(3), 253\u2013282 (2011)","journal-title":"Internat. J. Comput. Geom. Appl."},{"doi-asserted-by":"crossref","unstructured":"Buchin, K., Buchin, M., Meulemans, W., Mulzer, W.: Four soviets walk the dog - with an application to Alt\u2019s conjecture. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), pp. 1399\u20131413 (2014)","key":"44_CR8","DOI":"10.1137\/1.9781611973402.103"},{"doi-asserted-by":"crossref","unstructured":"Chen, D., Driemel, A., Guibas, L.J., Nguyen, A., Wenk, C.: Approximate map matching with respect to the Fr\u00e9chet distance. In: Proceedings of 13th Workshop on Algorithm Engineering and Experiments (ALENEX 2011), pp. 75\u201383 (2011)","key":"44_CR9","DOI":"10.1137\/1.9781611972917.8"},{"issue":"5","key":"44_CR10","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":"44_CR11","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."},{"unstructured":"Eiter, T., Mannila, H.: Computing discrete Fr\u00e9chet distance. Technical report. CD-TR 94\/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria (1994)","key":"44_CR12"},{"key":"44_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BFb0020793","volume-title":"STACS 91","author":"M Godau","year":"1991","unstructured":"Godau, M.: A natural metric for curves - computing the distance for polygonal chains and approximation algorithms. In: Jantzen, M., Choffrut, C. (eds.) STACS 1991. LNCS, vol. 480, pp. 127\u2013136. Springer, Heidelberg (1991)"},{"key":"44_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/978-3-642-40450-4_48","volume-title":"Algorithms \u2013 ESA 2013","author":"J Gudmundsson","year":"2013","unstructured":"Gudmundsson, J., Smid, M.: Fr\u00e9chet queries in geometric trees. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 565\u2013576. Springer, Heidelberg (2013)"},{"doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Raichel, B.: The Fr\u00e9chet distance revisited and extended. In: Proceedings of 27th Annual Symposium on Computational Geometry (SoCG 2011), pp. 448\u2013457 (2011)","key":"44_CR15","DOI":"10.1145\/1998196.1998269"},{"doi-asserted-by":"crossref","unstructured":"Munich, M.E., Perona, P.: Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification. In: Proceedings of the 7th International Conference on Computer Vision (ICCV 1999), pp. 108\u2013115 (1999)","key":"44_CR16","DOI":"10.1109\/ICCV.1999.791205"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48971-0_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T14:02:27Z","timestamp":1559311347000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48971-0_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662489703","9783662489710"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48971-0_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}