@online{Bringmann_arXiv1810.10982,
TITLE = {Fr{\'e}chet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability},
AUTHOR = {Bringmann, Karl and K{\"u}nnemann, Marvin and Nusser, Andr{\'e}},
LANGUAGE = {eng},
URL = {http://arxiv.org/abs/1810.10982},
EPRINT = {1810.10982},
EPRINTTYPE = {arXiv},
YEAR = {2018},
ABSTRACT = {The discrete Fr\'echet distance is a popular measure for comparing polygonal<br>curves. An important variant is the discrete Fr\'echet distance under<br>translation, which enables detection of similar movement patterns in different<br>spatial domains. For polygonal curves of length $n$ in the plane, the fastest<br>known algorithm runs in time $\tilde{\cal O}(n^{5})$ [Ben Avraham, Kaplan,<br>Sharir '15]. This is achieved by constructing an arrangement of disks of size<br>${\cal O}(n^{4})$, and then traversing its faces while updating reachability in<br>a directed grid graph of size $N := {\cal O}(n^2)$, which can be done in time<br>$\tilde{\cal O}(\sqrt{N})$ per update [Diks, Sankowski '07]. The contribution<br>of this paper is two-fold.<br> First, although it is an open problem to solve dynamic reachability in<br>directed grid graphs faster than $\tilde{\cal O}(\sqrt{N})$, we improve this<br>part of the algorithm: We observe that an offline variant of dynamic<br>$s$-$t$-reachability in directed grid graphs suffices, and we solve this<br>variant in amortized time $\tilde{\cal O}(N^{1/3})$ per update, resulting in an<br>improved running time of $\tilde{\cal O}(n^{4.66...})$ for the discrete<br>Fr\'echet distance under translation. Second, we provide evidence that<br>constructing the arrangement of size ${\cal O}(n^{4})$ is necessary in the<br>worst case, by proving a conditional lower bound of $n^{4 -- o(1)}$ on the<br>running time for the discrete Fr\'echet distance under translation, assuming<br>the Strong Exponential Time Hypothesis.<br>},
}