Computing the Fréchet distance between simple polygons

DOI10.1016/j.comgeo.2007.08.003zbMath1145.65009OpenAlexW2122005371MaRDI QIDQ934016

Maike Buchin, Carola Wenk, Kevin Buchin

Publication date: 29 July 2008

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2007.08.003

zbMATH Keywords

dynamic programmingpolynomial-time algorithmsimple polygonsshortest pathsFréchet distanceshape matching

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items

Computing the similarity between moving curves ⋮ Computing the Fréchet Distance Between Polygons with Holes ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance ⋮ Implicitization of curves and (hyper)surfaces using predicted support ⋮ Gromov-Fréchet distance between curves ⋮ Approximating ( k,ℓ )-Median Clustering for Polygonal Curves ⋮ Computing the Fréchet distance between simple polygons

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Can we compute the similarity between surfaces?
• Matrix multiplication via arithmetic progressions
• Computing the Fréchet distance between simple polygons
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Comparison of distance measures for planar curves
• Approximate matching of polygonal shapes
• Gaussian elimination is not optimal
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Slowing down sorting networks to obtain faster sorting algorithms
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS