LIPIcs.SoCG.2019.66.pdf
- Filesize: 0.68 MB
- 5 pages
Document
Fréchet View - A Tool for Exploring Fréchet Distance Algorithms (Multimedia Exposition)
Author
-
Part of:
Volume:
35th International Symposium on Computational Geometry (SoCG 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-06-11
File
Document Identifiers
Acknowledgements
This program was developed as part of my master thesis at the chair of Prof. Dr. André Schulz, supervised by Dr. Lena Schlipf.
Cite As Get BibTex
Peter Schäfer. Fréchet View - A Tool for Exploring Fréchet Distance Algorithms (Multimedia Exposition). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 66:1-66:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.66
Abstract
The Fréchet-distance is a similarity measure for geometric shapes. Alt and Godau presented the first algorithm for computing the Fréchet-distance and introduced a key concept, the free-space diagram. Since then, numerous variants of the Fréchet-distance have been studied. We present here an interactive, graphical tool for exploring some Fréchet-distance algorithms. Given two curves, users can experiment with the free-space diagram and compute the Fréchet-distance. The Fréchet-distance can be computed for two important classes of shapes: for polygonal curves in the plane, and for simple polygonal surfaces. Finally, we demonstrate an implementation of a very recent concept, the k-Fréchet-distance.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Fréchet distance
- free-space diagram
- polygonal curves
- simple polygons
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Hugo A. Akitaya, Maike Buchin, Leonie Ryvkin, and Jérôme Urhausen. The k-Fréchet distance revisited and extended. In 35th European Workshop on Computational Geometry, 2019. URL: http://www.eurocg2019.uu.nl/papers/41.pdf.
- Helmut Alt and Michael Godau. Computing the Fréchet Distance between two Polygonal Curves. International Journal of Computational Geometry and Applications, 5(1-2):75-91, 1995. URL: http://dx.doi.org/10.1142/S0218195995000064.
- Kevin Buchin, Maike Buchin, and Carola Wenk. Computing the Fréchet Distance Between Simple Polygons in Polynomial Time. In Proceedings of the Twenty-second Annual Symposium on Computational Geometry, SCG '06, pages 80-87, 2006. URL: http://dx.doi.org/10.1145/1137856.1137870.
- Maike Buchin and Leonie Ryvkin. The k-Fréchet distance of polygonal curves. In 34th European Workshop on Computational Geometry, 2018. URL: https://conference.imp.fu-berlin.de/eurocg18/download/paper_43.pdf.
- The CGAL Project. CGAL User and Reference Manual. CGAL Editorial Board, 4.12 edition, 2018. URL: https://doc.cgal.org/4.12/Manual/packages.html.