{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T16:54:48Z","timestamp":1778345688725,"version":"3.51.4"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T00:00:00Z","timestamp":1689292800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["1750780"],"award-info":[{"award-number":["1750780"]}]},{"DOI":"10.13039\/501100003246","name":"Dutch Research Council","doi-asserted-by":"crossref","award":["614.001.504, 628.011.005, 612.001.801"],"award-info":[{"award-number":["614.001.504, 628.011.005, 612.001.801"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,7,31]]},"abstract":"<jats:p>\n            In this article, we study a wide range of variants for computing the (discrete and continuous) Fr\u00e9chet distance between uncertain curves. An uncertain curve is a sequence of\n            <jats:italic>uncertainty regions,<\/jats:italic>\n            where each region is a disk, a line segment, or a set of points. A\n            <jats:italic>realisation<\/jats:italic>\n            of a curve is a polyline connecting one point from each region. Given an uncertain curve and a second (certain or uncertain) curve, we seek to compute the lower and upper bound Fr\u00e9chet distance, which are the minimum and maximum Fr\u00e9chet distance for any realisations of the curves.\n          <\/jats:p>\n          <jats:p>\n            We prove that both problems are NP-hard for the Fr\u00e9chet distance in several uncertainty models, and that the upper bound problem remains hard for the discrete Fr\u00e9chet distance. In contrast, the lower bound (discrete\u00a0[\n            <jats:xref ref-type=\"bibr\">5<\/jats:xref>\n            ] and continuous) Fr\u00e9chet distance can be computed in polynomial time in some models. Furthermore, we show that computing the expected (discrete and continuous) Fr\u00e9chet distance is #P-hard in some models.\n          <\/jats:p>\n          <jats:p>On the positive side, we present an FPTAS in constant dimension for the lower bound problem when \u0394\/\u03b4 is polynomially bounded, where \u03b4 is the Fr\u00e9chet distance and \u0394 bounds the diameter of the regions. We also show a near-linear-time 3-approximation for the decision problem on roughly \u03b4-separated convex regions. Finally, we study the setting with Sakoe\u2013Chiba time bands, where we restrict the alignment between the curves, and give polynomial-time algorithms for the upper bound and expected discrete and continuous Fr\u00e9chet distance for uncertainty modelled as point sets.<\/jats:p>","DOI":"10.1145\/3597640","type":"journal-article","created":{"date-parts":[[2023,5,23]],"date-time":"2023-05-23T11:59:43Z","timestamp":1684843183000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Fr\u00e9chet Distance for Uncertain Curves"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3022-7877","authenticated-orcid":false,"given":"Kevin","family":"Buchin","sequence":"first","affiliation":[{"name":"TU Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-7645-8367","authenticated-orcid":false,"given":"Chenglin","family":"Fan","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-9403-8856","authenticated-orcid":false,"given":"Maarten","family":"L\u00f6ffler","sequence":"additional","affiliation":[{"name":"Utrecht University, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0158-1746","authenticated-orcid":false,"given":"Aleksandr","family":"Popov","sequence":"additional","affiliation":[{"name":"TU Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6584-4843","authenticated-orcid":false,"given":"Benjamin","family":"Raichel","sequence":"additional","affiliation":[{"name":"University of Texas at Dallas, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1129-461X","authenticated-orcid":false,"given":"Marcel","family":"Roeloffzen","sequence":"additional","affiliation":[{"name":"TU Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,7,14]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","unstructured":"Manuel Abellanas Ferran Hurtado Christian Icking Rolf Klein Elmar Langetepe Lihong Ma Bel\u00e9n Palop and Vera Sacrist\u00e1n. 2001. Smallest color-spanning objects. In Algorithms\u2014ESA 2001 . Lecture Notes in Computer Science Vol. 2161. Springer 278\u2013289. DOI:10.1007\/3-540-44676-1_23","DOI":"10.1007\/3-540-44676-1_23"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2955098"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/130920526"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9903-x"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195912600023"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000064"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.05.011"},{"key":"e_1_3_2_9_2","unstructured":"Donald J. Berndt and James Clifford. 1994. Using dynamic time warping to find patterns in time series. In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining (AAAIWS\u201994) . 359\u2013370. https:\/\/aaai.org\/conference\/kdd\/kdd97\/."},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1109\/FOCS.2014.76","volume-title":"Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201914)","author":"Bringmann Karl","year":"2014","unstructured":"Karl Bringmann. 2014. Why walking the dog takes time. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201914). IEEE, Los Alamitos, CA, 661\u2013670. DOI:10.1109\/FOCS.2014.76"},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"2902","DOI":"10.1137\/1.9781611975482.180","volume-title":"Proceedings of the 30th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201919)","author":"Bringmann Karl","year":"2019","unstructured":"Karl Bringmann, Marvin K\u00fcnnemann, and Andr\u00e9 Nusser. 2019. Fr\u00e9chet distance under translation. In Proceedings of the 30th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201919). 2902\u20132921. DOI:10.5555\/3310435.3310615"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1080\/13658810903569598"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9878-7"},{"key":"e_1_3_2_14_2","doi-asserted-by":"crossref","first-page":"2922","DOI":"10.1137\/1.9781611975482.181","volume-title":"Proceedings of the 30th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201919)","author":"Buchin Kevin","year":"2019","unstructured":"Kevin Buchin, Anne Driemel, Joachim Gudmundsson, Michael Horton, Irina Kostitsyna, Maarten L\u00f6ffler, and Martijn Struijs. 2019. Approximating ( \\(k, \\ell\\) )-center clustering for curves. In Proceedings of the 30th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201919). 2922\u20132938. DOI:10.1137\/1.9781611975482.181"},{"key":"e_1_3_2_15_2","first-page":"496","volume-title":"Proceedings of the 27th International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201919)","author":"Buchin Kevin","year":"2019","unstructured":"Kevin Buchin, Anne Driemel, Natasja van de L\u2019Isle, and Andr\u00e9 Nusser. 2019. klcluster. In Proceedings of the 27th International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201919). ACM, New York, NY, 496\u2013499. DOI:10.1145\/3347146.3359111"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9430-0"},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","unstructured":"Kevin Buchin Maarten L\u00f6ffler Tim Ophelders Aleksandr Popov J\u00e9r\u00f4me Urhausen and Kevin Verbeek. 2023. Computing the Fr\u00e9chet distance between uncertain curves in one dimension. Computational Geometry 109 (2023) 101923. DOI:10.1016\/j.comgeo.2022.101923","DOI":"10.1016\/j.comgeo.2022.101923"},{"key":"e_1_3_2_18_2","volume-title":"Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201921) (Leibniz International Proceedings in Informatics)","author":"Buchin Kevin","year":"2021","unstructured":"Kevin Buchin, Maarten L\u00f6ffler, Aleksandr Popov, and Marcel Roeloffzen. 2021. Uncertain curve simplification. In Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201921) (Leibniz International Proceedings in Informatics), Filippo Bonchi and Simon J. Puglisi (Eds.). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, Article 26. DOI:10.4230\/LIPIcs.MFCS.2021.26"},{"key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"2887","DOI":"10.1137\/1.9781611975482.179","volume-title":"Proceedings of the 30th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201919)","author":"Buchin Kevin","year":"2019","unstructured":"Kevin Buchin, Tim Ophelders, and Bettina Speckmann. 2019. SETH says: Weak Fr\u00e9chet distance is faster, but only if it is continuous and in one dimension. In Proceedings of the 30th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201919). 2887\u20132901. DOI:10.1137\/1.9781611975482.179"},{"key":"e_1_3_2_20_2","first-page":"119","volume-title":"Proceedings of the 20th International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201912)","author":"Buchin Kevin","year":"2012","unstructured":"Kevin Buchin, Stef Sijben, T. Jean Marie Arseneau, and Erik P. Willems. 2012. Detecting movement patterns using Brownian bridges. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201912). ACM, New York, NY, 119\u2013128. DOI:10.1145\/2424321.2424338"},{"key":"e_1_3_2_21_2","first-page":"367","volume-title":"Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG\u201914)","author":"Buchin Maike","year":"2014","unstructured":"Maike Buchin, Anne Driemel, and Bettina Speckmann. 2014. Computing the Fr\u00e9chet distance with shortcuts is NP-hard. In Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG\u201914). ACM, New York, NY, 367\u2013376. DOI:10.1145\/2582112.2582144"},{"key":"e_1_3_2_22_2","unstructured":"Maike Buchin and Stef Sijben. 2016. Discrete Fr\u00e9chet distance for uncertain points. In Proceedings of the European Workshop on Computational Geometry (EuroCG\u201916) . http:\/\/www.eurocg2016.usi.ch\/sites\/default\/files\/paper_72.pdf."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195997000326"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195909003076"},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/3150919.3150924","volume-title":"Proceedings of the 6th ACM SIGSPATIAL Workshop on Analytics for Big Geospatial Data (BigSpatial\u201917)","author":"Devogele Thomas","year":"2017","unstructured":"Thomas Devogele, Laurent Etienne, Maxence Esnault, and Florian Lardy. 2017. Optimized discrete Fr\u00e9chet distance between trajectories. In Proceedings of the 6th ACM SIGSPATIAL Workshop on Analytics for Big Geospatial Data (BigSpatial\u201917). ACM, New York, NY, 11\u201319. DOI:10.1145\/3150919.3150924"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/120865112"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9402-z"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.20382\/jocg.v4i1a3"},{"key":"e_1_3_2_29_2","volume-title":"Computing Discrete Fr\u00e9chet Distance","author":"Eiter Thomas","year":"1994","unstructured":"Thomas Eiter and Heikki Mannila. 1994. Computing Discrete Fr\u00e9chet Distance. Technical Report CD-TR 94\/64. Technische Universit\u00e4t Wien. http:\/\/www.kr.tuwien.ac.at\/staff\/eiter\/et-archive\/cdtr9464.pdf."},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/2462356.2462395","volume-title":"Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG\u201913)","author":"Evans William","year":"2013","unstructured":"William Evans, David Kirkpatrick, Maarten L\u00f6ffler, and Frank Staals. 2013. Competitive query strategies for minimising the ply of the potential locations of moving points. In Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG\u201913). ACM, New York, NY, 155\u2013164. DOI:10.1145\/2462356.2462395"},{"key":"e_1_3_2_31_2","doi-asserted-by":"crossref","unstructured":"Chenglin Fan Jun Luo and Binhai Zhu. 2013. Tight approximation bounds for connectivity with a color-spanning set. In Algorithms and Computation . Lecture Notes in Computer Science Vol. 8283. Springer 590\u2013600. DOI:10.1007\/978-3-642-45030-3_55","DOI":"10.1007\/978-3-642-45030-3_55"},{"key":"e_1_3_2_32_2","first-page":"Article 42, 16","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917) (Leibniz International Proceedings in Informatics)","author":"Fan Chenglin","year":"2017","unstructured":"Chenglin Fan and Benjamin Raichel. 2017. Computing the Fr\u00e9chet gap distance. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917) (Leibniz International Proceedings in Informatics), Boris Aronov and Matthew J. Katz (Eds.). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, Article 42, 16 pages. DOI:10.4230\/LIPIcs.SoCG.2017.42"},{"key":"e_1_3_2_33_2","unstructured":"Chenglin Fan and Binhai Zhu. 2018. Complexity and algorithms for the discrete Fr\u00e9chet distance upper bound with imprecise input. arXiv:cs.CG\/1509.02576v2 (2018)."},{"key":"e_1_3_2_34_2","first-page":"Article 20, 14","volume-title":"Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT\u201918) (Leibniz International Proceedings in Informatics)","author":"Filtser Omrit","year":"2018","unstructured":"Omrit Filtser and Matthew J. Katz. 2018. Algorithms for the discrete Fr\u00e9chet distance under translation. In Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT\u201918) (Leibniz International Proceedings in Informatics), David Eppstein (Ed.). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, Article 20, 14 pages. DOI:10.4230\/LIPIcs.SWAT.2018.20"},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","unstructured":"Michael Godau. 1991. A natural metric for curves\u2014Computing the distance for polygonal chains and approximation algorithms. In STACS 91 . Lecture Notes in Computer Science Vol. 480. Springer 127\u2013136. DOI:10.1007\/BFb0020793","DOI":"10.1007\/BFb0020793"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.02.002"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195919500043"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195993000257"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2532646"},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","unstructured":"Allan J\u00f8rgensen Jeff M. Phillips and Maarten L\u00f6ffler. 2011. Geometric computations on indecisive points. In Algorithms and Data Structures . Lecture Notes in Computer Science Vol. 6844. Springer 536\u2013547. DOI:10.1007\/978-3-642-22300-6_45","DOI":"10.1007\/978-3-642-22300-6_45"},{"key":"e_1_3_2_41_2","doi-asserted-by":"crossref","unstructured":"Eamonn Keogh and Chotirat Ann Ratanamahatana. 2005. Exact indexing of dynamic time warping. Knowledge and Information Systems 7 3 (2005) 358\u2013386. DOI:10.1007\/s10115-004-0154-9","DOI":"10.1007\/s10115-004-0154-9"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.01.039"},{"key":"e_1_3_2_43_2","doi-asserted-by":"crossref","unstructured":"John Krumm. 2009. A survey of computational location privacy. Personal and Ubiquitous Computing 13 6 (2009) 391\u2013399. DOI:10.1007\/s00779-008-0212-5","DOI":"10.1007\/s00779-008-0212-5"},{"key":"e_1_3_2_44_2","volume-title":"Data Imprecision in Computational Geometry","author":"L\u00f6ffler Maarten","year":"2009","unstructured":"Maarten L\u00f6ffler. 2009. Data Imprecision in Computational Geometry. Ph.D. Dissertation. Universiteit Utrecht. https:\/\/dspace.library.uu.nl\/bitstream\/handle\/1874\/36022\/loffler.pdf."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.20382\/jocg.v5i1a1"},{"key":"e_1_3_2_46_2","doi-asserted-by":"crossref","unstructured":"Maarten L\u00f6ffler and Jack Scott Snoeyink. 2010. Delaunay triangulations of imprecise points in linear time after preprocessing. Computational Geometry 43 3 (2010) 234\u2013242. DOI:10.1016\/j.comgeo.2008.12.007","DOI":"10.1016\/j.comgeo.2008.12.007"},{"key":"e_1_3_2_47_2","doi-asserted-by":"crossref","unstructured":"Maarten L\u00f6ffler and Marc van Kreveld. 2006. Largest and smallest tours and convex hulls for imprecise points. In Algorithm Theory\u2014SWAT 2006 . Lecture Notes in Computer Science Vol. 4059. Springer 375\u2013387. DOI:10.1007\/11785293_35","DOI":"10.1007\/11785293_35"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.09.008"},{"key":"e_1_3_2_49_2","first-page":"15","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB\u201907)","author":"Pei Jian","year":"2007","unstructured":"Jian Pei, Bin Jiang, Xuemin Lin, and Yidong Yuan. 2007. Probabilistic skylines on uncertain data. In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB\u201907). 15\u201326."},{"key":"e_1_3_2_50_2","doi-asserted-by":"crossref","unstructured":"Dieter Pfoser and Christian S. Jensen. 1999. Capturing the uncertainty of moving-object representations. In Advances in Spatial Databases . Lecture Notes in Computer Science Vol. 1651. Springer 111\u2013131. DOI:10.1007\/3-540-48482-5_9","DOI":"10.1007\/3-540-48482-5_9"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1978.1163055"},{"key":"e_1_3_2_52_2","unstructured":"Jeff Sember and William Evans. 2008. Guaranteed Voronoi diagrams of uncertain sites. In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG\u201909) ."},{"key":"e_1_3_2_53_2","doi-asserted-by":"crossref","unstructured":"Aravinda Prasad Sistla Ouri Wolfson Sam Chamberlain and Son Dao. 1998. Querying the uncertain position of moving objects. In Temporal Databases . Lecture Notes in Computer Science Vol. 1399. Springer 310\u2013337. DOI:10.1007\/BFb0053708","DOI":"10.1007\/BFb0053708"},{"key":"e_1_3_2_54_2","doi-asserted-by":"crossref","unstructured":"Subhash Suri Kevin Verbeek and Hakan Y\u0131ld\u0131z. 2013. On the most likely convex hull of uncertain points. In Algorithms\u2014ESA 2013 . Lecture Notes in Computer Science Vol. 8125. Springer 791\u2013802. DOI:10.1007\/978-3-642-40450-4_67","DOI":"10.1007\/978-3-642-40450-4_67"},{"key":"e_1_3_2_55_2","first-page":"Article 67, 14","volume-title":"Proceedings of the 27th Annual European Symposium on Algorithms (ESA\u201919) (Leibniz International Proceedings in Informatics)","author":"Kerkhof Mees van de","year":"2019","unstructured":"Mees van de Kerkhof, Irina Kostitsyna, Maarten L\u00f6ffler, Majid Mirzanezhad, and Carola Wenk. 2019. Global curve simplification. In Proceedings of the 27th Annual European Symposium on Algorithms (ESA\u201919) (Leibniz International Proceedings in Informatics), Michael A. Bender, Ola Svensson, and Grzegorz Herman (Eds.). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, Article 67, 14 pages. DOI:10.4230\/LIPIcs.ESA.2019.67"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1137\/090753620"},{"key":"e_1_3_2_57_2","first-page":"Article 56, 14","volume-title":"Proceedings of the 34th International Symposium on Computational Geometry (SoCG\u201918) (Leibniz International Proceedings in Informatics)","author":"Kreveld Marc van","year":"2018","unstructured":"Marc van Kreveld, Maarten L\u00f6ffler, and Lionov Wiratma. 2018. On optimal polyline simplification using the Hausdorff and Fr\u00e9chet distance. In Proceedings of the 34th International Symposium on Computational Geometry (SoCG\u201918) (Leibniz International Proceedings in Informatics), Bettina Speckmann and Csaba D. T\u00f3th (Eds.). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, Article 56, 14 pages. DOI:10.4230\/LIPIcs.SoCG.2018.56"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.135"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3597640","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3597640","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:41Z","timestamp":1750182521000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3597640"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,14]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,7,31]]}},"alternative-id":["10.1145\/3597640"],"URL":"https:\/\/doi.org\/10.1145\/3597640","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,14]]},"assertion":[{"value":"2021-11-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}