License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.36
URN: urn:nbn:de:0030-drops-160448
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16044/
Driemel, Anne ;
van der Hoog, Ivor ;
Rotenberg, Eva
On the Discrete Fréchet Distance in a Graph
Abstract
The Fréchet distance is a well-studied similarity measure between curves that is widely used throughout computer science. Motivated by applications where curves stem from paths and walks on an underlying graph (such as a road network), we define and study the Fréchet distance for paths and walks on graphs. When provided with a distance oracle of G with O(1) query time, the classical quadratic-time dynamic program can compute the Fréchet distance between two walks P and Q in a graph G in O(|P|⋅|Q|) time. We show that there are situations where the graph structure helps with computing Fréchet distance: when the graph G is planar, we apply existing (approximate) distance oracles to compute a (1+ε)-approximation of the Fréchet distance between any shortest path P and any walk Q in O(|G|log|G|/√ε+|P|+|Q|/ε) time. We generalise this result to near-shortest paths, i.e. κ-straight paths, as we show how to compute a (1+ε)-approximation between a κ-straight path P and any walk Q in O(|G|log|G|/√ε+|P|+(κ|Q|)/ε) time. Our algorithmic results hold for both the strong and the weak discrete Fréchet distance over the shortest path metric in G.
Finally, we show that additional assumptions on the input, such as our assumption on path straightness, are indeed necessary to obtain truly subquadratic running time. We provide a conditional lower bound showing that the Fréchet distance, or even its 1.01-approximation, between arbitrary paths in a weighted planar graph cannot be computed in O((|P|⋅|Q|)^{1-δ}) time for any δ > 0 unless the Orthogonal Vector Hypothesis fails. For walks, this lower bound holds even when G is planar, unit-weight and has O(1) vertices.
BibTeX - Entry
@InProceedings{driemel_et_al:LIPIcs.SoCG.2022.36,
author = {Driemel, Anne and van der Hoog, Ivor and Rotenberg, Eva},
title = {{On the Discrete Fr\'{e}chet Distance in a Graph}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {36:1--36:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-227-3},
ISSN = {1868-8969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16044},
URN = {urn:nbn:de:0030-drops-160448},
doi = {10.4230/LIPIcs.SoCG.2022.36},
annote = {Keywords: Fr\'{e}chet, graphs, planar, complexity analysis}
}
|
Keywords: |
|
Fréchet, graphs, planar, complexity analysis |
|
Collection: |
|
38th International Symposium on Computational Geometry (SoCG 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.06.2022 |
