English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The discrete Fr\'echet distance is a popular measure for comparing polygonalcurves. An important variant is the discrete Fr\'echet distance undertranslation, which enables detection of similar movement patterns in differentspatial domains. For polygonal curves of length $n$ in the plane, the fastestknown 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 ina 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 contributionof this paper is two-fold.  First, although it is an open problem to solve dynamic reachability indirected grid graphs faster than $\tilde{\cal O}(\sqrt{N})$, we improve thispart of the algorithm: We observe that an offline variant of dynamic$s$-$t$-reachability in directed grid graphs suffices, and we solve thisvariant in amortized time $\tilde{\cal O}(N^{1/3})$ per update, resulting in animproved running time of $\tilde{\cal O}(n^{4.66...})$ for the discreteFr\'echet distance under translation. Second, we provide evidence thatconstructing the arrangement of size ${\cal O}(n^{4})$ is necessary in theworst case, by proving a conditional lower bound of $n^{4 - o(1)}$ on therunning time for the discrete Fr\'echet distance under translation, assumingthe Strong Exponential Time Hypothesis.

Fr\'echet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability