Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability

DOI10.1137/1.9781611975482.180zbMath1432.68497OpenAlexW2949439292MaRDI QIDQ5236372

Marvin Künnemann, Karl Bringmann, 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

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

Related Items (5)

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

This page was built for publication: Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability