A faster algorithm for the discrete Fr\'echet distance under translation

Understand

The discrete Fr\'echet distance is a useful similarity measure for comparing two sequences of points $P=(p_1,\ldots, p_m)$ and $Q=(q_1,\ldots,q_n)$.

• In many applications, the quality of the matching can be improved if we let $Q$ undergo some transformation relative to $P$.
• In this paper we consider the problem of finding a translation of $Q$ that brings the discrete Fr\'echet distance between $P$ and $Q$ to a minimum.
• We devise an algorithm that computes the minimum discrete Fr\'echet distance under translation in $\mathbb{R}^2$, and runs in $O(m^3n^2(1+\log(n/m))\log(m+n))$ time, assuming $m\leq n$.