Fréchet similarity of closed polygonal curves

DOI10.1142/S0218195916500035zbMATH Open1341.68299arXiv1505.04093OpenAlexW2264989043MaRDI QIDQ2809314FDOQ2809314

Authors: V. M. Yakovenko, M. Schlesinger, E. V. Vodolazskiy 

Publication date: 27 May 2016

Published in: International Journal of Computational Geometry \& Applications (Search for Journal in Brave)

Abstract: The article analyzes similarity of closed polygonal curves with respect to the Frechet metric, which is stronger than the well-known Hausdorff metric and therefore is more appropriate in some applications. An algorithm is described that determines whether the Frechet distance between two closed polygonal curves with m and n vertices is less than a given number. The algorithm takes O(mn) time whereas the previously known algorithms take O(mn log(mn)) time.

Full work available at URL: https://arxiv.org/abs/1505.04093

Recommendations

• Recognizing the similarity of polygons in a strengthened Hausdorff metric
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Fréchet distance with speed limits
• Approximately matching polygonal curves with respect to the Fréchet distance
• Fréchet Distance for Curves, Revisited

zbMATH Keywords

closed polygonal curvesFréchet similarity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES

Cited In (6)

• Voronoi diagram of polygonal chains under the discrete Fréchet distance
• Similarity of polygonal curves in the presence of outliers
• Generalized Similar Frenet Curves
• Recognizing the similarity of polygons in a strengthened Hausdorff metric
• Gromov-Fréchet distance between curves
• Discrete Fréchet distance for closed curves

This page was built for publication: Fréchet similarity of closed polygonal curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2809314)