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

DOI10.1137/1.9781611975482.180zbMATH Open1432.68497OpenAlexW2949439292MaRDI QIDQ5236372FDOQ5236372

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

Recommendations

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

Mathematics Subject Classification ID

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

Cited In (6)

• When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation
• Fine-grained complexity theory: conditional lower bounds for computational geometry
• Translation invariant Fréchet distance queries
• Fréchet Distance for Uncertain Curves
• Computing the Fréchet gap distance
• Algorithms for the discrete Fréchet distance under translation

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)