Driemel, Anne ;
van der Hoog, Ivor ;
Rotenberg, Eva
On the Discrete Fréchet Distance in a Graph
Abstract
The Fréchet distance is a wellstudied 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 quadratictime 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(GlogG/√ε+P+Q/ε) time. We generalise this result to nearshortest 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(GlogG/√ε+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.01approximation, 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, unitweight 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:136:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772273},
ISSN = {18688969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16044},
URN = {urn:nbn:de:0030drops160448},
doi = {10.4230/LIPIcs.SoCG.2022.36},
annote = {Keywords: Fr\'{e}chet, graphs, planar, complexity analysis}
}
01.06.2022
Keywords: 

Fréchet, graphs, planar, complexity analysis 
Seminar: 

38th International Symposium on Computational Geometry (SoCG 2022)

Issue date: 

2022 
Date of publication: 

01.06.2022 