Document Open Access Logo

On Computing the Fréchet Distance Between Surfaces

Authors Amir Nayyeri, Hanzhong Xu

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.55.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Amir Nayyeri
Hanzhong Xu

Cite As Get BibTex

Amir Nayyeri and Hanzhong Xu. On Computing the Fréchet Distance Between Surfaces. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.55

Abstract

We describe two (1+epsilon)-approximation algorithms for computing the Fréchet distance between two homeomorphic piecewise linear surfaces R and S of genus zero and total complexity n, with Frechet distance delta.

(1) A 2^{O((n + ( (Area(R)+Area(S))/(epsilon.delta)^2 )^2 )} time algorithm if R and S are composed of fat triangles (triangles with angles larger than a constant).

(2) An O(D/(epsilon.delta)^2) n + 2^{O(D^4/(epsilon^4.delta^2))} time algorithm if R and S are polyhedral terrains over [0,1]^2 with slope at most D.

Although, the Fréchet distance between curves has been studied extensively, very little is known for surfaces. Our results are the first algorithms (both for surfaces and terrains) that are guaranteed to terminate in finite time. Our latter result, in particular, implies a linear time algorithm for terrains of constant maximum slope and constant Frechet distance.

Subject Classification

Keywords
  • Surfaces
  • Terrains
  • Frechet distance
  • Parametrized complexity
  • normal coordinates

Metrics

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

References

  1. Helmut Alt and Maike Buchin. Semi-computability of the Fréchet distance between surfaces. In Proceedings of the 21st European Workshop on Computational Geometery, pages 45-48, 2005. Google Scholar
  2. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. Int. J. Comput. Geometry Appl., 5:75-91, 1995. URL: http://dx.doi.org/10.1142/S0218195995000064.
  3. Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, and Carola Wenk. Fréchet distance for curves, revisited. In Proceedings of the 14th Conference on Annual European Symposium, pages 52-63, 2006. URL: http://dx.doi.org/10.1007/11841036_8.
  4. Rinat Ben Avraham, Omrit Filtser, Haim Kaplan, Matthew J. Katz, and Micha Sharir. The discrete fréchet distance with shortcuts via approximate distance counting and selection. In Proceedings of the 30th Annual Symposium on Computational Geometry, pages 377-386, 2014. URL: http://dx.doi.org/10.1145/2582112.2582155.
  5. Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. On map-matching vehicle tracking data. In Proceedings of the 31st Conference on Very Large Data Bases, pages 853-864, 2005. Google Scholar
  6. Kevin Buchin, Maike Buchin, and Joachim Gudmundsson. Detecting single file movement. In Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 1-10, 2008. Google Scholar
  7. Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Maarten Löffler, and Jun Luo. Detecting commuting patterns by clustering subtrajectories. In Proceedings of the 19th International Symposium on Algorithms and Computation, pages 644-655, 2008. Google Scholar
  8. Kevin Buchin, Maike Buchin, and André Schulz. Fréchet distance of surfaces: Some simple hard cases. In Proceedings of the 18th Conference on Annual European Symposium, pages 63-74, 2010. Google Scholar
  9. Kevin Buchin, Maike Buchin, and Carola Wenk. Computing the Fréchet distance between simple polygons. Comp. Geom. Theo. Appl., 41(1-2):2-20, October 2008. URL: http://dx.doi.org/10.1016/j.comgeo.2007.08.003.
  10. Atlas F. Cook IV, Anne Driemel, Jessica Sherette, and Carola Wenk. Computing the frechet distance between folded polygons. Computational Geometry, 50:1-16, 2015. URL: http://dx.doi.org/10.1016/j.comgeo.2015.08.002.
  11. Anne Driemel and Sariel Har-Peled. Jaywalking your dog: Computing the fréchet distance with shortcuts. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 318-337, 2012. Google Scholar
  12. 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, 2012. URL: http://dx.doi.org/10.1007/s00454-012-9402-z.
  13. Thomas Eiter and Heikki Mannila. Computing discrete Fréchet distance. Tech. Report CD-TR 94/64, Christian Doppler Lab. Expert Sys., TU Vienna, Austria, 1994. Google Scholar
  14. Jeff Erickson and Amir Nayyeri. Shortest non-crossing walks in the plane. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 297-308, 2011. Google Scholar
  15. Jeff Erickson and Amir Nayyeri. Tracing compressed curves in triangulated surfaces. In Proceedings of the 28th Annual Symposium on Computational Geometry, pages 131-140, 2012. Google Scholar
  16. Michael S. Floater and Kai Hormann. Surface parameterization: a tutorial and survey. In Advances in Multiresolution for Geometric Modelling, Mathematics and Visualization, pages 157-186. Springer Berlin Heidelberg, 2005. URL: http://dx.doi.org/10.1007/3-540-26808-1_9.
  17. Michael Godau. On the Complexity of Measuring the Similarity Between Geometric Objects in Higher Dimensions. PhD thesis, Freie Universität Berlin, 1998. Google Scholar
  18. Wolfgang Haken. Theorie der Normalflächen: Ein Isotopiekriterium für den Kreisknoten. Acta Mathematica, 105:245-375, 1961. Google Scholar
  19. Sariel Har-Peled and Benjamin Raichel. The fréchet distance revisited and extended. ACM Transactions on Algorithms, 10(1):3, 2014. URL: http://dx.doi.org/10.1145/2532646.
  20. Man-Soon Kim, Sang-Wook Kim, and Miyoung Shin. Optimization of subsequence matching under time warping in time-series databases. In Proceedings of ACM Symposium on Applied Computing, pages 581-586, 2005. Google Scholar
  21. Ariane Mascret, Thomas Devogele, Iwan Le Berre, and Alain Hénaff. Coastline matching process based on the discrete Fréchet distance. In Proceedings of the12th International symposium on Spatial Data Handling, pages 383-400, 2006. Google Scholar
  22. Amir Nayyeri and Anastasios Sidiropoulos. Computing the fréchet distance between polygons with holes. In The proceedings of The 42nd International Colloquium on Automata, Languages, and Programming, pages 997-1009, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_81.
  23. Marcus Schaefer, Eric Sedgwick, and Daniel Stefankovic. Algorithms for normal curves and surfaces. In Proceedings if the 8th Annual International Computing and Combinatorics Conference, pages 370-380, 2002. Google Scholar
  24. Marcus Schaefer and Daniel Štefankovič. Decidability of string graphs. J. Comput. Syst. Sci., 68(2):319-334, 2004. Google Scholar
  25. Joan Serrà, Emillia Gómez, Perfecto Herrera, and Xavier Serra. Chroma binary similarity and local alignment applied to cover song identification. IEEE Transactions on Audio, Speech & Language Processing, 16(6):1138-1151, 2008. Google Scholar
  26. Daniel Stefankovic. Algorithms for Simple Curves on Surfaces, String Graphs, and Crossing Numbers. PhD thesis, University of Chicago, Chicago, IL, USA, 2005. AAI3168396. Google Scholar
  27. Oliver van Kaick, Hao Zhang, Ghassan Hamarneh, and Daniel Cohen-Or. A survey on shape correspondence. Computer Graphics Forum, 30(6):1681-1707, 2011. Google Scholar
  28. Carola Wenk, Randall Salas, and Dieter Pfoser. 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., pages 879-888, 2006. Google Scholar
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 About DROPS Imprint Privacy Contact