Faster Fréchet Distance under Transformations

Abstract

We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves $\ddot{I}€$ and $\ddot{I}ƒ$ of total complexity $n$ and a threshold $\hat{I}´\ge 0$, we present an $\tilde{\mathcal{O}}(n^{7+\frac{1}{3}})$ time algorithm to determine whether there exists a translation $t\in {\mathbb{R}}^2$ such that the Fréchet distance between $\ddot{I}€$ and $\ddot{I}ƒ+t$ is at most $\hat{I}´$. This improves on the previous best result, which is an $\mathcal{O}(n^8)$ time algorithm. We then generalize this result to any class of rationally parameterized transformations, which includes translation, rotation, scaling, and arbitrary affine transformations. For a class $\mathcal{T}$ of rationally parametrized transformations with $k$ degrees of freedom, we show that one can determine whether there is a transformation $\ddot{I}„\in \mathcal{T}$ such that the Fréchet distance between $\ddot{I}€$ and $\ddot{I}„(\ddot{I}ƒ)$ is at most $\hat{I}´$ in $\tilde{\mathcal{O}}(n^{3k+\frac{4}{3}})$ time.

under submission