{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T19:23:46Z","timestamp":1773170626097,"version":"3.50.1"},"reference-count":63,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,2,27]],"date-time":"2017-02-27T00:00:00Z","timestamp":1488153600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["MU\/3501\/1"],"award-info":[{"award-number":["MU\/3501\/1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["MU\/3501\/2"],"award-info":[{"award-number":["MU\/3501\/2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.022.707"],"award-info":[{"award-number":["639.022.707"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["612.001.106"],"award-info":[{"award-number":["612.001.106"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000921","name":"European Cooperation in Science and Technology","doi-asserted-by":"publisher","award":["IC0903 MOVE"],"award-info":[{"award-number":["IC0903 MOVE"]}],"id":[{"id":"10.13039\/501100000921","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":[[2017,7]]},"DOI":"10.1007\/s00454-017-9878-7","type":"journal-article","created":{"date-parts":[[2017,2,27]],"date-time":"2017-02-27T11:47:51Z","timestamp":1488196071000},"page":"180-216","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Four Soviets Walk the Dog: Improved Bounds for Computing the Fr\u00e9chet Distance"],"prefix":"10.1007","volume":"58","author":[{"given":"Kevin","family":"Buchin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maike","family":"Buchin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wouter","family":"Meulemans","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1948-5840","authenticated-orcid":false,"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,2,27]]},"reference":[{"issue":"2","key":"9878_CR1","doi-asserted-by":"crossref","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":"3\u20134","key":"9878_CR2","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/s00453-005-1165-y","volume":"42","author":"PK Agarwal","year":"2005","unstructured":"Agarwal, P.K., Har-Peled, S., Mustafa, N.H., Wang, Y.: Near-linear time approximation algorithms for curve simplification. Algorithmica 42(3\u20134), 203\u2013219 (2005)","journal-title":"Algorithmica"},{"issue":"6","key":"9878_CR3","doi-asserted-by":"crossref","first-page":"2039","DOI":"10.1137\/120890855","volume":"42","author":"PK Agarwal","year":"2013","unstructured":"Agarwal, P.K., Matou\u0161ek, J., Sharir, M.: On range searching with semialgebraic sets. II. SIAM J. Comput. 42(6), 2039\u20132062 (2013)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9878_CR4","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1145\/1059513.1059515","volume":"52","author":"N Ailon","year":"2005","unstructured":"Ailon, N., Chazelle, B.: Lower bounds for linear degeneracy testing. J. ACM 52(2), 157\u2013171 (2005)","journal-title":"J. ACM"},{"issue":"1","key":"9878_CR5","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1006\/inco.1997.2632","volume":"136","author":"S Albers","year":"1997","unstructured":"Albers, S., Hagerup, T.: Improved parallel integer sorting without concurrent writing. Inf. Comput. 136(1), 25\u201351 (1997)","journal-title":"Inf. Comput."},{"key":"9878_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/978-3-642-03456-5_16","volume-title":"Efficient Algorithms","author":"H Alt","year":"2009","unstructured":"Alt, H.: The computational geometry of comparing shapes. In: Albers, S., Alt, H., N\u00e4her, S. (eds.) Efficient Algorithms. Lecture Notes in Computer Science, vol. 5760, pp. 235\u2013248. Springer, Berlin (2009)"},{"issue":"1","key":"9878_CR7","doi-asserted-by":"crossref","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."},{"issue":"1\u20132","key":"9878_CR8","doi-asserted-by":"crossref","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."},{"issue":"1","key":"9878_CR9","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s00453-003-1042-5","volume":"38","author":"H Alt","year":"2003","unstructured":"Alt, H., Knauer, C., Wenk, C.: Comparison of distance measures for planar curves. Algorithmica 38(1), 45\u201358 (2003)","journal-title":"Algorithmica"},{"key":"9878_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/11841036_8","volume-title":"Algorithms\u2014ESA 2006","author":"B Aronov","year":"2006","unstructured":"Aronov, B., Har-Peled, S., Knauer, C., Wang, Y., Wenk, C.: Fr\u00e9chet distances for curves, revisited. In: Azar, Y., Erlebach, T. (eds.) Algorithms\u2014ESA 2006. Lecture Notes in Computer Science, vol. 4168, pp. 52\u201363. Springer, Berlin (2006)"},{"key":"9878_CR11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity. Cambridge University Press, Cambridge (2009)"},{"issue":"4","key":"9878_CR12","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1007\/s00453-007-9036-3","volume":"50","author":"I Baran","year":"2008","unstructured":"Baran, I., Demaine, E.D., P\u0103tra\u015fcu, M.: Subquadratic algorithms for 3SUM. Algorithmica 50(4), 584\u2013596 (2008)","journal-title":"Algorithmica"},{"issue":"2","key":"9878_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TAC.1959.1104847","volume":"4","author":"R Bellman","year":"1959","unstructured":"Bellman, R., Kalaba, R.: On adaptive control processes. IRE Trans. Autom. Control 4(2), 1\u20139 (1959)","journal-title":"IRE Trans. Autom. Control"},{"issue":"4","key":"9878_CR14","first-page":"29","volume":"11","author":"R Ben Avraham","year":"2015","unstructured":"Ben Avraham, R., Filtser, O., Kaplan, H., Katz, M.J., Sharir, M.: He discrete and semicontinuous Fr\u00e9chet distance with shortcuts via approximate distance counting and selection. ACM Trans. Algorithms 11(4), 29 (2015)","journal-title":"ACM Trans. Algorithms"},{"key":"9878_CR15","first-page":"853","volume-title":"Proceedings of the 31st VLDB Conference","author":"S Brakatsoulas","year":"2005","unstructured":"Brakatsoulas, S., Pfoser, D., Salas, R., Wenk, C.: On map-matching vehicle tracking data. In: B\u00f6hm, K., et al. (eds.) Proceedings of the 31st VLDB Conference, pp. 853\u2013864. ACM, New York (2005)"},{"issue":"2","key":"9878_CR16","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1007\/s00453-012-9734-3","volume":"69","author":"D Bremner","year":"2012","unstructured":"Bremner, D., Chan, T.M., Demaine, E.D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., P\u0103tra\u015fcu, M., Taslakian, P.: Necklaces, convolutions, and $$X+Y$$ X + Y . Algorithmica 69(2), 294\u2013314 (2012)","journal-title":"Algorithmica"},{"key":"9878_CR17","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\u2014FOCS 2014, pp. 661\u2013670. IEEE Computer Society, Los Alamitos (2014)","DOI":"10.1109\/FOCS.2014.76"},{"issue":"2","key":"9878_CR18","first-page":"46","volume":"7","author":"K Bringmann","year":"2016","unstructured":"Bringmann, K., Mulzer, W.: Approximability of the discrete Fr\u00e9chet distance. J. Comput. Geom. 7(2), 46\u201376 (2016)","journal-title":"J. Comput. Geom."},{"issue":"7","key":"9878_CR19","first-page":"1101","volume":"24","author":"K Buchin","year":"2010","unstructured":"Buchin, K., Buchin, M., Gudmundsson, J.: Constrained free space diagrams: a tool for trajectory analysis. Int. J. GIS 24(7), 1101\u20131125 (2010)","journal-title":"Int. J. GIS"},{"issue":"3","key":"9878_CR20","doi-asserted-by":"crossref","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":"9878_CR21","first-page":"170","volume-title":"23rd EuroCG\/FWCG","author":"K Buchin","year":"2007","unstructured":"Buchin, K., Buchin, M., Knauer, C., Rote, G., Wenk, C.: How difficult is it to walk the dog? In: Aichholzer, O., Hackl, T. (eds.) 23rd EuroCG\/FWCG, pp. 170\u2013173. Technischen Universit\u00e4t Graz, Graz (2007)"},{"key":"9878_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/978-3-642-33090-2_21","volume-title":"Algorithms\u2014ESA 2012","author":"K Buchin","year":"2012","unstructured":"Buchin, K., Buchin, M., Meulemans, W., Speckmann, B.: Locally correct Fr\u00e9chet matchings. In: Epstein, L., Ferragina, P. (eds.) Algorithms\u2014ESA 2012. Lecture Notes in Computer Science, vol. 7501, pp. 229\u2013240. Springer, Heidelberg (2012)"},{"key":"9878_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/978-3-642-15781-3_6","volume-title":"Algorithms\u2014ESA 2010. Part II","author":"K Buchin","year":"2010","unstructured":"Buchin, K., Buchin, M., Schulz, A.: Fr\u00e9chet distance of surfaces: some simple hard cases. In: de Berg, M., Meyer, U. (eds.) Algorithms\u2014ESA 2010. Part II. Lecture Notes in Computer Science, vol. 6347, pp. 63\u201374. Springer, Berlin (2010)"},{"issue":"2","key":"9878_CR24","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/s00454-016-9800-8","volume":"56","author":"K Buchin","year":"2016","unstructured":"Buchin, K., Buchin, M., van Leusden, R., Meulemans, W., Mulzer, W.: Computing the Fr\u00e9chet distance with a retractable leash. Discrete Comput. Geom. 56(2), 315\u2013336 (2016)","journal-title":"Discrete Comput. Geom."},{"key":"9878_CR25","doi-asserted-by":"crossref","unstructured":"Buchin, K., Buchin, M., Wang, Y.: Exact algorithms for partial curve matching via the Fr\u00e9chet distance. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 645\u2013654. SIAM, Philadelphia (2009)","DOI":"10.1137\/1.9781611973068.71"},{"issue":"1\u20132","key":"9878_CR26","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.comgeo.2007.08.003","volume":"41","author":"K Buchin","year":"2008","unstructured":"Buchin, K., Buchin, M., Wenk, C.: Computing the Fr\u00e9chet distance between simple polygons. Comput. Geom. 41(1\u20132), 2\u201320 (2008)","journal-title":"Comput. Geom."},{"issue":"2","key":"9878_CR27","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/1944345.1944347","volume":"58","author":"K Buchin","year":"2011","unstructured":"Buchin, K., Mulzer, W.: Delaunay triangulations in $$O({\\rm sort}(n))$$ O ( sort ( n ) ) time and more. J. ACM 58(2), 6 (2011)","journal-title":"J. ACM"},{"key":"9878_CR28","unstructured":"Buchin, M.: On the Computability of the Fr\u00e9chet Distance Between Triangulated Surfaces. PhD thesis, Free University Berlin, Berlin (2007). http:\/\/www.diss.fu-berlin.de\/diss\/receive\/FUDISS_thesis_000000002618"},{"issue":"3","key":"9878_CR29","doi-asserted-by":"crossref","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, \u00c9., 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. 43(3), 295\u2013311 (2010)","journal-title":"Comput. Geom."},{"issue":"2","key":"9878_CR30","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1007\/s00453-007-9062-1","volume":"50","author":"TM Chan","year":"2008","unstructured":"Chan, T.M.: All-pairs shortest paths with real weights in $${O}(n^3 \/ \\log n)$$ O ( n 3 \/ log n ) time. Algorithmica 50(2), 236\u2013243 (2008)","journal-title":"Algorithmica"},{"issue":"5","key":"9878_CR31","doi-asserted-by":"crossref","first-page":"2075","DOI":"10.1137\/08071990X","volume":"39","author":"TM Chan","year":"2010","unstructured":"Chan, T.M.: More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput. 39(5), 2075\u20132089 (2010)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"9878_CR32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02238188","volume":"36","author":"BM Chazelle","year":"1986","unstructured":"Chazelle, B.M., Lee, D.T.: On a circle placement problem. Computing 36(1\u20132), 1\u201316 (1986)","journal-title":"Computing"},{"key":"9878_CR33","series-title":"Lecture Notes in Computer Science","first-page":"267","volume-title":"Algorithms and Data Structures","author":"AF Cook IV","year":"2011","unstructured":"Cook IV, A.F., Driemel, A., Har-Peled, S., Sherette, J., Wenk, C.: Computing the Fr\u00e9chet distance between folded polygons. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 6844, pp. 267\u2013278. Springer, Heidelberg (2011)"},{"issue":"1","key":"9878_CR34","first-page":"9","volume":"7","author":"AF Cook IV","year":"2010","unstructured":"Cook IV, A.F., Wenk, C.: Geodesic Fr\u00e9chet distance inside a simple polygon. ACM Trans. Algorithms 7(1), 9 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"6","key":"9878_CR35","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1016\/j.comgeo.2012.11.006","volume":"46","author":"M Berg de","year":"2013","unstructured":"de Berg, M., Cook IV, A.F., Gudmundsson, J.: Fast Fr\u00e9chet queries. Comput. Geom. 46(6), 747\u2013755 (2013)","journal-title":"Comput. Geom."},{"issue":"5","key":"9878_CR36","doi-asserted-by":"crossref","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":"9878_CR37","doi-asserted-by":"crossref","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."},{"issue":"4","key":"9878_CR38","doi-asserted-by":"crossref","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(4), 535\u2013569 (2002)","journal-title":"Discrete Comput. Geom."},{"key":"9878_CR39","unstructured":"Eiter, T., Mannila, H.: Computing Discrete Fr\u00e9chet Distance. Technical report CD-TR 94\/65, Christian Doppler Laboratory (1994)"},{"key":"9878_CR40","first-page":"8","volume":"1999","author":"J Erickson","year":"1999","unstructured":"Erickson, J.: Bounds for linear satisfiability problems. Chic. J. Theor. Comput. Sci. 1999, 8 (1999)","journal-title":"Chic. J. Theor. Comput. Sci."},{"key":"9878_CR41","doi-asserted-by":"crossref","unstructured":"Fredman, M.L.: How good is the information theory bound in sorting? Theor. Comput. Sci. 1(4), 355\u2013361 (1975\/76)","DOI":"10.1016\/0304-3975(76)90078-5"},{"issue":"3","key":"9878_CR42","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"ML Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information-theoretic bound with fusion trees. J. Comput. Syst. Sci. 47(3), 424\u2013436 (1993)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9878_CR43","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"ML Fredman","year":"1984","unstructured":"Fredman, M.L., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17(1), 13\u201327 (1984)","journal-title":"Math. Syst. Theory"},{"issue":"3","key":"9878_CR44","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of $${O}(n^2)$$ O ( n 2 ) problems in computational geometry. Comput. Geom. 5(3), 165\u2013185 (1995)","journal-title":"Comput. Geom."},{"key":"9878_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BFb0020793","volume-title":"STACS 91","author":"M Godau","year":"1991","unstructured":"Godau, M.: A natural metric for curves\u2014computing the distance for polygonal chains and approximation algorithms. In: Choffrut, C., Jantzen, M. (eds.) STACS 91. Lecture Notes in Computer Science, vol. 480, pp. 127\u2013136. Springer, Berlin (1991)"},{"key":"9878_CR46","unstructured":"Godau, M.: On the Complexity of Measuring the Similarity Between Geometric Objects in Higher Dimensions. PhD thesis, Free University Berlin, Berlin (1998)"},{"key":"9878_CR47","unstructured":"Gudmundsson, J., Wolle, T.: Towards automated football analysis: algorithms and data structures. In: Proceedings of the 10th Australasian Conference on Mathematics and Computers in Sport 2010. ANZIAM, Darwin (2010)"},{"key":"9878_CR48","first-page":"121","volume-title":"Computational Geometry (SCG\u201912)","author":"S Har-Peled","year":"2012","unstructured":"Har-Peled, S., Nayyeri, A., Salavatipour, M., Sidiropoulos, A.: How to walk your dog in the mountains with no magic leash. In: Dey, T., Whitesides, S. (eds.) Computational Geometry (SCG\u201912), pp. 121\u2013130. ACM, New York (2012)"},{"issue":"1","key":"9878_CR49","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/2532646","volume":"10","author":"S Har-Peled","year":"2014","unstructured":"Har-Peled, S., Raichel, B.: The Fr\u00e9chet distance revisited and extended. ACM Trans. Algorithms 10(1), 3 (2014)","journal-title":"ACM Trans. Algorithms"},{"issue":"8","key":"9878_CR50","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1145\/359138.359141","volume":"22","author":"DS Hirschberg","year":"1979","unstructured":"Hirschberg, D.S., Chandra, A.K., Sarwate, D.V.: Computing connected components on parallel computers. Commun. ACM 22(8), 461\u2013464 (1979)","journal-title":"Commun. ACM"},{"key":"9878_CR51","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Approximate nearest neighbor algorithms for Frechet distance via product metrics. In: Computational Geometry (SCG\u201902), pp. 102\u2013106. ACM, New York (2002)","DOI":"10.1145\/513400.513414"},{"key":"9878_CR52","doi-asserted-by":"crossref","unstructured":"Gr\u00f8nlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. In: 55th Annual IEEE Symposium on Foundations of Computer Science\u2014FOCS 2014, pp. 621\u2013630. IEEE Computer Society, Los Alamitos (2014)","DOI":"10.1109\/FOCS.2014.72"},{"issue":"5","key":"9878_CR53","doi-asserted-by":"crossref","first-page":"1384","DOI":"10.1137\/S0097539794268649","volume":"26","author":"MJ Katz","year":"1997","unstructured":"Katz, M.J., Sharir, M.: An expander-based approach to geometric optimization. SIAM J. Comput. 26(5), 1384\u20131408 (1997)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9878_CR54","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/j.comgeo.2010.09.008","volume":"44","author":"A Maheshwari","year":"2011","unstructured":"Maheshwari, A., Sack, J.-R., Shahbaz, K., Zarrabi-Zadeh, H.: Fr\u00e9chet distance with speed limits. Comput. Geom. 44(2), 110\u2013120 (2011)","journal-title":"Comput. Geom."},{"key":"9878_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"518","DOI":"10.1007\/978-3-642-23719-5_44","volume-title":"Algorithms\u2014ESA 2011","author":"A Maheshwari","year":"2011","unstructured":"Maheshwari, A., Sack, J.-R., Shahbaz, K., Zarrabi-Zadeh, H.: Improved algorithms for partial curve matching. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) Algorithms\u2014ESA 2011. Lecture Notes in Computer Science, vol. 6942, pp. 518\u2013529. Springer, Heidelberg (2011)"},{"key":"9878_CR56","series-title":"Texts and Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry. Texts and Monographs in Computer Science. Springer, New York (1985)"},{"key":"9878_CR57","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu, M.: Towards polynomial lower bounds for dynamic problems. In: STOC\u201910, pp. 603\u2013610. ACM, New York (2010)","DOI":"10.1145\/1806689.1806772"},{"key":"9878_CR58","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1007\/3-540-09510-1_42","volume-title":"Automata, Languages and Programming","author":"A Sch\u00f6nhage","year":"1979","unstructured":"Sch\u00f6nhage, A.: On the power of random access machines. In: Maurer, H.A. (ed.) Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 71, pp. 520\u2013529. Springer, Berlin (1979)"},{"issue":"3","key":"9878_CR59","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1137\/0209036","volume":"9","author":"A Sch\u00f6nhage","year":"1980","unstructured":"Sch\u00f6nhage, A.: Storage modification machines. SIAM J. Comput. 9(3), 490\u2013508 (1980)","journal-title":"SIAM J. Comput."},{"key":"9878_CR60","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge (1995)"},{"issue":"2","key":"9878_CR61","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"RE Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. Assoc. Comput. Mach. 22(2), 215\u2013225 (1975)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"9878_CR62","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jagm.2002.1211","volume":"42","author":"M Thorup","year":"2002","unstructured":"Thorup, M.: Randomized sorting in $${O}(n \\log \\log n)$$ O ( n log log n ) time and linear space using addition, shift, and bit-wise Boolean operations. J. Algorithms 42(2), 205\u2013230 (2002)","journal-title":"J. Algorithms"},{"key":"9878_CR63","doi-asserted-by":"crossref","unstructured":"Wenk, C., Salas, R., Pfoser, D.: Addressing the need for map-matching speed: localizing global curve-matching algorithms. In: Proceedings of the 18th International Conference on Scientific and Statistical Database Management, pp. 379\u2013388. IEEE Computer Society, Los Alamitos (2006)","DOI":"10.1109\/SSDBM.2006.11"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-017-9878-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9878-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9878-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T00:25:21Z","timestamp":1568852721000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-017-9878-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,27]]},"references-count":63,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["9878"],"URL":"https:\/\/doi.org\/10.1007\/s00454-017-9878-7","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2,27]]}}}