Computing the Fréchet distance with a retractable leash (Q312142)

Let \(P\) and \(Q\) be two homothetic curves in \(\mathbb{R}^d\). Given a metric on \(\mathbb{R}^d\), the maximum of the distances between homothetic points of \(P\) and \(Q\) can be computed for every orientation-preserving homeomorphism that transforms \(P\) into \(Q\). The Fréchet distance measures the similarity of \(P\) and \(Q\) by the infimum of such maxima. This paper improves the computation of the Fréchet distance of two piecewise-linear curves with vertices \(m\) and \(n\), respectively, by using an original framework that does not rely on a decision problem. It takes quadratic time for polyhedral distances, and \(O(mn(d+ \log^2 m+\log^2 n))\) for the Euclidean case. Besides, a (\(1+\epsilon\))-approximation under the Euclidean metric is deduced from the polyhedral distance implementation. It is conjectured that the approach could be useful in order to obtain a quadratic algorithm for the Euclidean case and as well as to improve the search of a homeomorphism that provides the Fréchet distance.