Fréchet distance under translation: conditional hardness and an algorithm via offline dynamic grid reachability

DOI10.1137/1.9781611975482.180MaRDI QIDQ5236372zbMATH OpenOpenAlexFDO

Authors Karl Bringmann, Marvin Künnemann, André Nusser

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611975482.180

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• scientific article; zbMATH DE number 7238975
• Algorithms for the discrete Fréchet distance under translation
• Translation invariant Fréchet distance queries

Cited in

(10)

• Computing the Fréchet gap distance
• Fine-grained complexity theory: conditional lower bounds for computational geometry
• Translation invariant Fréchet distance queries
• Discrete Fréchet Distance under Translation
• Algorithms for the discrete Fréchet distance under translation
• When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation
• Fréchet Distance for Uncertain Curves
• Fréchet distance for uncertain curves
• Translating Hausdorff is hard: fine-grained lower bounds for Hausdorff distance under translation
• Fine-grained hardness for edit distance to a fixed sequence

This page was built for publication: Fréchet distance under translation: conditional hardness and an algorithm via offline dynamic grid reachability

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