hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
The discrete Fr\'echet distance is a popular measure for comparing polygonal
curves. An important variant is the discrete Fr\'echet distance under
translation, which enables detection of similar movement patterns in different
spatial domains. For polygonal curves of length $n$ in the plane, the fastest
known algorithm runs in time $\tilde{\cal O}(n^{5})$ [Ben Avraham, Kaplan,
Sharir '15]. This is achieved by constructing an arrangement of disks of size
${\cal O}(n^{4})$, and then traversing its faces while updating reachability in
a directed grid graph of size $N := {\cal O}(n^2)$, which can be done in time
$\tilde{\cal O}(\sqrt{N})$ per update [Diks, Sankowski '07]. The contribution
of this paper is two-fold.
First, although it is an open problem to solve dynamic reachability in
directed grid graphs faster than $\tilde{\cal O}(\sqrt{N})$, we improve this
part of the algorithm: We observe that an offline variant of dynamic
$s$-$t$-reachability in directed grid graphs suffices, and we solve this
variant in amortized time $\tilde{\cal O}(N^{1/3})$ per update, resulting in an
improved running time of $\tilde{\cal O}(n^{4.66...})$ for the discrete
Fr\'echet distance under translation. Second, we provide evidence that
constructing the arrangement of size ${\cal O}(n^{4})$ is necessary in the
worst case, by proving a conditional lower bound of $n^{4 - o(1)}$ on the
running time for the discrete Fr\'echet distance under translation, assuming
the Strong Exponential Time Hypothesis.
