An improved approximation algorithm for the discrete Fréchet distance

DOI10.1016/j.ipl.2018.06.011zbMath1461.68239OpenAlexW2810388706MaRDI QIDQ1653046

Timothy M. Chan, Zahed Rahmati

Publication date: 17 July 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.06.011

zbMATH Keywords

approximation algorithmdiscrete Fréchet distancestrongly subquadratic time

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items

Approximating the geometric edit distance ⋮ Unnamed Item ⋮ Fine-grained complexity theory: conditional lower bounds for computational geometry

Cites Work

• Unnamed Item
• Approximability of the discrete Fréchet distance
• Approximation schemes for covering and packing problems in image processing and VLSI
• Algorithms on Strings, Trees and Sequences
• Polynomial-time approximation schemes for packing and piercing fat objects
• Computing the Discrete Fréchet Distance in Subquadratic Time