Fréchet Distance in Unweighted Planar Graphs

Abstract

The Fréchet distance is a distance measure between trajectories in Rd or walks in a graph G. Given constant-time shortest path queries, the Discrete Fréchet distance DG(P, Q) between two walks P and Q can be computed in O(|P | · |Q|) time using a dynamic program. Driemel, van der Hoog, and Rotenberg [SoCG’22] show that for weighted planar graphs this approach is likely tight, as there can be no strongly-subquadratic algorithm to compute a 1.01-approximation of DG(P, Q) unless the Orthogonal Vector Hypothesis (OVH) fails. Such quadratic-time conditional lower bounds are common to many Fréchet distance variants. However, they can be circumvented by assuming that the input comes from some well-behaved class: There exist (1 + ε)-approximations, both in weighted graphs and in Rd, that take near-linear time for c-packed or κ-straight walks in the graph. In Rd there also exists a near-linear time algorithm to compute the Fréchet distance whenever all input edges are long compared to the distance. We consider computing the Fréchet distance in unweighted planar graphs. We show that there exist no strongly-subquadratic 1.25-approximations of the discrete Fréchet distance between two disjoint simple paths in an unweighted planar graph in strongly subquadratic time, unless OVH fails. This improves the previous lower bound, both in terms of generality and approximation factor. We subsequently show that adding graph structure circumvents this lower bound: If the graph is a regular tiling with unit-weighted edges, then there exists an Õ((|P | + |Q|)1.5)-time algorithm to compute DG(P, Q). Our result has natural implications in the plane, as it allows us to define a new class of well-behaved curves that facilitate (1 + ε)-approximations of their discrete Fréchet distance in subquadratic time.