On the discrete Fréchet distance in a graph.

The Fréchet distance is a well-studied similarity measure between curves thatis widely used throughout computer science. Motivated by applications where curves stemfrom paths and walks on an underlying graph (such as a road network), we define and studythe Fréchet distance for paths and walks on graphs. When provided with a distance oracleofGwithO(1)query time, the classical quadratic-time dynamic program can compute theFréchet distance between two walksPandQin a graphGinO(|P|·|Q|)time. We showthat there are situations where the graph structure helps with computing Fréchet distance:when the graphGis planar, we apply existing (approximate) distance oracles to computea(1 +ε)-approximation of the Fréchet distance between any shortest pathPand any walkQinO(|G|log|G|/ε+|P|+|Q|ε2)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 pathPand any walkQinO(|G|log|G|/ε+|P|+κ|Q|ε2)time. Specifically, for the(strong) Fréchet distance, we show how to preprocess the graph and the trajectoryPinO(|G|log|G|/ε+|P|)time such that, for anyQ, we can compute a(1 +ε)approximationof the Fréchet distance betweenPandQinO(κ|Q|ε2)time.Finally, we show that additional assumptions on the input, such as our assumptionon path straightness, are indeed necessary to obtain truly subquadratic running time. Weprovide a conditional lower bound showing that the Fréchet distance, or even its1.01-approximation, between arbitrarypathsin a weighted planar graph cannot be computed inO((|P|·|Q|)1−δ)time for anyδ >0unless the Orthogonal Vector Hypothesis fails. Forwalks, this lower bound holds even whenGis planar, unit-weight and hasO(1)vertices