Document Open Access Logo

Fréchet Distance for Uncertain Curves

Authors Kevin Buchin , Chenglin Fan, Maarten Löffler, Aleksandr Popov , Benjamin Raichel , Marcel Roeloffzen

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.20.pdf
  • Filesize: 0.73 MB
  • 20 pages

Document Identifiers

Author Details

Kevin Buchin
  • Department of Mathematics and Computer Science, TU Eindhoven, Netherlands
Chenglin Fan
  • Department of Computer Science, University of Texas at Dallas, Richardson, TX, USA
Maarten Löffler
  • Department of Information and Computing Sciences, Utrecht University, Netherlands
Aleksandr Popov
  • Department of Mathematics and Computer Science, TU Eindhoven, Netherlands
Benjamin Raichel
  • Department of Computer Science, University of Texas at Dallas, Richardson, TX, USA
Marcel Roeloffzen
  • Department of Mathematics and Computer Science, TU Eindhoven, Netherlands

Funding

  • Fan, Chenglin: NSF CRII Award 1566137 and CAREER Award 1750780
  • Popov, Aleksandr: Netherlands Organisation for Scientific Research (NWO), project no. 612.001.801
  • Raichel, Benjamin: NSF CRII Award 1566137 and CAREER Award 1750780
  • Roeloffzen, Marcel: Netherlands Organisation for Scientific Research (NWO), project no. 628.011.005

Cite AsGet BibTex

Kevin Buchin, Chenglin Fan, Maarten Löffler, Aleksandr Popov, Benjamin Raichel, and Marcel Roeloffzen. Fréchet Distance for Uncertain Curves. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.20

Abstract

In this paper we study a wide range of variants for computing the (discrete and continuous) Fréchet distance between uncertain curves. We define an uncertain curve as a sequence of uncertainty regions, where each region is a disk, a line segment, or a set of points. A realisation 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échet distance, which are the minimum and maximum Fréchet distance for any realisations of the curves. We prove that both problems are NP-hard for the continuous Fréchet distance, and the upper bound problem remains hard for the discrete Fréchet distance. In contrast, the lower bound discrete Fréchet distance can be computed in polynomial time using dynamic programming. Furthermore, we show that computing the expected discrete or continuous Fréchet distance is #P-hard when the uncertainty regions are modelled as point sets or line segments. On the positive side, we argue that in any constant dimension there is a FPTAS for the lower bound problem when Δ/δ is polynomially bounded, where δ is the Fréchet distance and Δ bounds the diameter of the regions. We then argue there is a near-linear-time 3-approximation for the decision problem when the regions are convex and roughly δ-separated. Finally, we study the setting with Sakoe - Chiba bands, restricting the alignment of the two curves, and give polynomial-time algorithms for upper bound and expected (discrete) Fréchet distance for point-set-modelled uncertainty regions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Curves
  • Uncertainty
  • Fréchet Distance
  • Hardness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Manuel Abellanas, Ferran Hurtado, Christian Icking, Rolf Klein, Elmar Langetepe, Lihong Ma, Belén Palop, and Vera Sacristán. Smallest color-spanning objects. In Algorithms - ESA 2001, volume 2161 of Lecture Notes in Computer Science, pages 278-289, Berlin, Germany, 2001. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/3-540-44676-1_23.
  2. Pankaj K. Agarwal, Boris Aronov, Sariel Har-Peled, Jeff M. Phillips, Ke Yi, and Wuzhou Zhang. Nearest-neighbor searching under uncertainty II. ACM Transactions on Algorithms (TALG), 13(1):3:1-3:25, December 2016. URL: https://doi.org/10.1145/2955098.
  3. Pankaj K. Agarwal, Rinat Ben Avraham, Haim Kaplan, and Micha Sharir. Computing the discrete Fréchet distance in subquadratic time. SIAM Journal on Computing, 43(2):429-449, 2014. URL: https://doi.org/10.1137/130920526.
  4. Pankaj K. Agarwal, Alon Efrat, Swaminathan Sankararaman, and Wuzhou Zhang. Nearest-neighbor searching under uncertainty I. Discrete & Computational Geometry, 58(3):705-745, July 2017. URL: https://doi.org/10.1007/s00454-017-9903-x.
  5. Hee-Kap Ahn, Christian Knauer, Marc Scherfenberg, Lena Schlipf, and Antoine Vigneron. Computing the discrete Fréchet distance with imprecise input. International Journal of Computational Geometry & Applications, 22(01):27-44, 2012. URL: https://doi.org/10.1142/S0218195912600023.
  6. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry and Applications, 5(1):75-91, 1995. URL: https://doi.org/10.1142/S0218195995000064.
  7. Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew J. Katz, Joseph S.B. Mitchell, and Marina Simakov. Selecting and covering colored points. Discrete Applied Mathematics, 250:75-86, December 2018. URL: https://doi.org/10.1016/j.dam.2018.05.011.
  8. Donald J. Berndt and James Clifford. Using dynamic time warping to find patterns in time series. In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining, pages 359-370, Palo Alto, CA, USA, 1994. AAAI Press. URL: https://doi.org/10.5555/3000850.3000887.
  9. Karl Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 661-670, Piscataway, NJ, USA, August 2014. IEEE. URL: https://doi.org/10.1109/FOCS.2014.76.
  10. Karl Bringmann, Marvin Künnemann, and André Nusser. Fréchet distance under translation: Conditional hardness and an algorithm via offline dynamic grid reachability. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pages 2902-2921. Society for Industrial and Applied Mathematics, January 2019. URL: https://doi.org/10.5555/3310435.3310615.
  11. Kevin Buchin, Maike Buchin, and Joachim Gudmundsson. Constrained free space diagrams: A tool for trajectory analysis. International Journal of Geographical Information Science, 24(7):1101-1125, July 2010. URL: https://doi.org/10.1080/13658810903569598.
  12. Kevin Buchin, Maike Buchin, Wouter Meulemans, and Wolfgang Mulzer. Four Soviets walk the dog: Improved bounds for computing the Fréchet distance. Discrete & Computational Geometry, 58(1):180-216, 2017. URL: https://doi.org/10.1007/s00454-017-9878-7.
  13. Kevin Buchin, Chenglin Fan, Maarten Löffler, Aleksandr Popov, Benjamin Raichel, and Marcel Roeloffzen. Fréchet distance for uncertain curves, April 2020. URL: http://arxiv.org/abs/2004.11862.
  14. Kevin Buchin, Maarten Löffler, Pat Morin, and Wolfgang Mulzer. Preprocessing imprecise points for Delaunay triangulation: Simplified and extended. Algorithmica, 61(3):674-693, November 2011. URL: https://doi.org/10.1007/s00453-010-9430-0.
  15. Kevin Buchin, Tim Ophelders, and Bettina Speckmann. SETH says: Weak Fréchet distance is faster, but only if it is continuous and in one dimension. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '19), pages 2887-2901. Society for Industrial and Applied Mathematics, January 2019. URL: https://doi.org/10.5555/3310435.3310614.
  16. Maike Buchin, Anne Driemel, and Bettina Speckmann. Computing the Fréchet distance with shortcuts is NP-hard. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry (SoCG 2014), pages 367-376, New York, NY, USA, June 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2582112.2582144.
  17. Sandip Das, Partha P. Goswami, and Subhas C. Nandy. Smallest color-spanning object revisited. International Journal of Computational Geometry & Applications, 19(5):457-478, October 2009. URL: https://doi.org/10.1142/S0218195909003076.
  18. Thomas Devogele, Laurent Etienne, Maxence Esnault, and Florian Lardy. Optimized discrete Fréchet distance between trajectories. In Proc. 6th ACM SIGSPATIAL Workshop on Analytics for Big Geospatial Data, pages 11-19, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3150919.3150924.
  19. Anne Driemel and Sariel Har-Peled. Jaywalking your dog: Computing the Fréchet distance with shortcuts. SIAM Journal on Computing, 42(5):1830-1866, October 2018. URL: https://doi.org/10.1137/120865112.
  20. Anne Driemel, Sariel Har-Peled, and Carola Wenk. Approximating the Fréchet distance for realistic curves in near linear time. Discrete & Computational Geometry, 48(1):94-127, July 2012. URL: https://doi.org/s00454-012-9402-z.
  21. Anne Driemel, Herman Haverkort, Maarten Löffler, and Rodrigo I. Silveira. Flow computations on imprecise terrains. Journal of Computational Geometry (JoCG), 4(1):38-78, 2013. URL: https://doi.org/10.20382/jocg.v4i1a3.
  22. Thomas Eiter and Heikki Mannila. Computing discrete Fréchet distance. Technical Report CD-TR 94/64, Technishe Universität Wien, April 1994. URL: http://www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf [cited 2019-04-23]. URL: http://www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf.
  23. Chenglin Fan, Jun Luo, and Binhai Zhu. Tight approximation bounds for connectivity with a color-spanning set. In Algorithms and Computation (ISAAC 2013), volume 8283 of Lecture Notes in Computer Science, pages 590-600, Berlin, Germany, 2013. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-45030-3_55.
  24. Chenglin Fan and Benjamin Raichel. Computing the Fréchet gap distance. In 33rd International Symposium on Computational Geometry (SoCG 2017), volume 77 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1-42:16, Dagstuhl, Germany, 2017. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2017.42.
  25. Chenglin Fan and Binhai Zhu. Complexity and algorithms for the discrete Fréchet distance upper bound with imprecise input, February 2018. URL: http://arxiv.org/abs/1509.02576v2.
  26. Omrit Filtser and Matthew J. Katz. Algorithms for the discrete Fréchet distance under translation. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), volume 101 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1-20:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SWAT.2018.20.
  27. Michael Godau. A natural metric for curves: Computing the distance for polygonal chains and approximation algorithms. In STACS 91: Proceedings of 8th Annual Symposium on Theoretical Aspects of Computer Science, volume 480 of Lecture Notes in Computer Science, pages 127-136, Berlin, Germany, 1991. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/BFb0020793.
  28. Chris Gray, Frank Kammer, Maarten Löffler, and Rodrigo I. Silveira. Removing local extrema from imprecise terrains. Computational Geometry, 45(7):334-349, 2012. URL: https://doi.org/10.1016/j.comgeo.2012.02.002.
  29. Joachim Gudmundsson, Majid Mirzanezhad, Ali Mohades, and Carola Wenk. Fast Fréchet distance between curves with long edges. International Journal of Computational Geometry & Applications, 29(2):161-187, 2019. URL: https://doi.org/10.1142/S0218195919500043.
  30. Leonidas J. Guibas, John E. Hershberger, Joseph S. B. Mitchell, and Jack S. Snoeyink. Approximating polygons and subdivisions with minimum-link paths. International Journal of Computational Geometry & Applications, 3(4):383-415, 1993. URL: https://doi.org/10.1142/S0218195993000257.
  31. Sariel Har-Peled and Benjamin Raichel. The Fréchet distance revisited and extended. ACM Transactions on Algorithms (TALG), 10(1):3:1-3:22, January 2014. URL: https://doi.org/10.1145/2532646.
  32. Allan Jørgensen, Jeff Phillips, and Maarten Löffler. Geometric computations on indecisive points. In Algorithms and Data Structures (WADS 2011), volume 6844 of Lecture Notes in Computer Science, pages 536-547, Berlin, Germany, 2011. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-22300-6_45.
  33. Eamonn Keogh and Chotirat Ann Ratanamahatana. Exact indexing of dynamic time warping. Knowledge and Information Systems, 7(3):358-386, 2005. URL: https://doi.org/10.1007/s10115-004-0154-9.
  34. Christian Knauer, Maarten Löffler, Marc Scherfenberg, and Thomas Wolle. The directed Hausdorff distance between imprecise point sets. Theoretical Computer Science, 412(32):4173-4186, 2011. URL: https://doi.org/10.1016/j.tcs.2011.01.039.
  35. John Krumm. A survey of computational location privacy. Personal and Ubiquitous Computing, 13(6):391-399, August 2009. URL: https://doi.org/10.1007/s00779-008-0212-5.
  36. Maarten Löffler. Data Imprecision in Computational Geometry. PhD thesis, Universiteit Utrecht, October 2009. URL: https://dspace.library.uu.nl/bitstream/handle/1874/36022/loffler.pdf [cited 2019-06-15]. URL: https://dspace.library.uu.nl/bitstream/handle/1874/36022/loffler.pdf.
  37. Maarten Löffler and Wolfgang Mulzer. Unions of onions: Preprocessing imprecise points for fast onion decomposition. Journal of Computational Geometry (JoCG), 5(1):1-13, 2014. URL: https://doi.org/10.20382/jocg.v5i1a1.
  38. Maarten Löffler and Jack Snoeyink. Delaunay triangulations of imprecise points in linear time after preprocessing. Computational Geometry: Theory and Applications, 43(3):234-242, 2010. URL: https://doi.org/10.1016/j.comgeo.2008.12.007.
  39. Maarten Löffler and Marc van Kreveld. Largest and smallest tours and convex hulls for imprecise points. In Algorithm Theory - SWAT 2006, volume 4059 of Lecture Notes in Computer Science, pages 375-387, Berlin, Germany, 2006. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/11785293_35.
  40. Anil Maheshwari, Jörg-Rüdiger Sack, Kaveh Shahbaz, and Hamid Zarrabi-Zadeh. Fréchet distance with speed limits. Computational Geometry, 44(2):110-120, 2011. URL: https://doi.org/10.1016/j.comgeo.2010.09.008.
  41. Jian Pei, Bin Jiang, Xuemin Lin, and Yidong Yuan. Probabilistic skylines on uncertain data. In Proceedings of the 33rd International Conference on Very Large Data Bases, pages 15-26. VLDB Endowment, September 2007. URL: https://doi.org/10.5555/1325851.1325858.
  42. Dieter Pfoser and Christian S. Jensen. Capturing the uncertainty of moving-object representations. In Advances in Spatial Databases, volume 1651 of Lecture Notes in Computer Science, pages 111-131, Berlin, Germany, June 1999. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/3-540-48482-5_9.
  43. A. Prasad Sistla, Ouri Wolfson, Sam Chamberlain, and Son Dao. Querying the uncertain position of moving objects. In Temporal Databases: Research and Practice, volume 1399 of Lecture Notes in Computer Science, pages 310-337. Springer Berlin Heidelberg, Berlin, Germany, 1998. URL: https://doi.org/10.1007/BFb0053708.
  44. Hiroaki Sakoe and Seibi Chiba. Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing, 26(1):43-49, February 1978. URL: https://doi.org/10.1109/TASSP.1978.1163055.
  45. Jeff Sember and William Evans. Guaranteed Voronoi diagrams of uncertain sites. In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG 2008), pages 203-206, 2008. URL: http://cccg.ca/proceedings/2008/paper50full.pdf.
  46. Subhash Suri, Kevin Verbeek, and Hakan Yıldız. On the most likely convex hull of uncertain points. In Algorithms - ESA 2013, volume 8125 of Lecture Notes in Computer Science, pages 791-802, Berlin, Germany, 2013. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-40450-4_67.
  47. Marc van Kreveld, Maarten Löffler, and Joseph S. B. Mitchell. Preprocessing imprecise points and splitting triangulations. SIAM Journal on Computing, 39(7):2990-3000, May 2010. URL: https://doi.org/10.1137/090753620.
  48. Man Lung Yiu, Nikos Mamoulis, Xiangyuan Dai, Yufei Tao, and Michail Vaitis. Efficient evaluation of probabilistic advanced spatial queries on existentially uncertain data. IEEE Transactions on Knowledge and Data Engineering, 21(1):108-122, 2009. URL: https://doi.org/10.1109/TKDE.2008.135.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact