# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1810.10982.pdf

(Preprint), 2MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Bringmann, K., Künnemann, M., & Nusser, A. (2018). Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability. Retrieved from http://arxiv.org/abs/1810.10982.

Cite as: https://hdl.handle.net/21.11116/0000-0002-9E35-1

##### 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.

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.