Tight Fréchet bounds for $\lambda$-low density curves

Abstract

The Fréchet distance is a well-studied similarity measure between curves. We computing the Fréchet distance between $\lambda$-low-density curves, the most general of realistic curve assumptions, where every ball of radius $r$ intersects at most $\lambda$ edges of length at least $r$. Previous algorithms either assumed constant $\lambda$ or had no tight dependence on $\lambda$. For two $n$-vertex $\lambda$-low-density curves in ${\mathbb{R}}^d$, we give a $(1+\epsilon )$-approximation algorithm for the continuous and discrete Fréchet distance running in $\tilde{O}\left(\frac{{\lambda }^{2/d}{n}^{2-2/d}}{{\epsilon }^2}\right)$ time. Our key insight is a tight property of simplifying $\lambda$-low density curves: the simplification of any $n$-vertex $\lambda$-low-density curve is $O({\lambda }^{1/d}{n}^{1-1/d})$-low-density. We show this is tight, and this provides the structural property under simplification that was previously known for $c$-packed curves. We provide matching lower bounds for $n$ and $\lambda$: assuming the Orthogonal Vectors Hypothesis, for every $\delta >0$, we rule out algorithms with running time $O\left({\left(\frac{{\lambda }^{2/d}{n}^{2-2/d}}{{\epsilon }^{2-4/d}}\right)}^{1-\delta }\right).$ We extend our techniques to the map matching problem, where we also give tight bounds.