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

Consider the natural question of how to measure the similarity of curves inthe plane by a quantity that is invariant under translations of the curves.Such a measure is justified whenever we aim to quantify the similarity of thecurves' shapes rather than their positioning in the plane, e.g., to compare thesimilarity of handwritten characters. Perhaps the most natural such notion isthe (discrete) Fr\'echet distance under translation. Unfortunately, thealgorithmic literature on this problem yields a very pessimistic view: Onpolygonal curves with $n$ vertices, the fastest algorithm runs in time$O(n^{4.667})$ and cannot be improved below $n^{4-o(1)}$ unless the StrongExponential Time Hypothesis fails. Can we still obtain an implementation thatis efficient on realistic datasets?  Spurred by the surprising performance of recent implementations for theFr\'echet distance, we perform algorithm engineering for the Fr\'echet distanceunder translation. Our solution combines fast, but inexact tools fromcontinuous optimization (specifically, branch-and-bound algorithms for globalLipschitz optimization) with exact, but expensive algorithms from computationalgeometry (specifically, problem-specific algorithms based on an arrangementconstruction). We combine these two ingredients to obtain an exact decisionalgorithm for the Fr\'echet distance under translation. For the related task ofcomputing the distance value up to a desired precision, we engineer and comparedifferent methods. On a benchmark set involving handwritten characters androute trajectories, our implementation answers a typical query for either taskin the range of a few milliseconds up to a second on standard desktop hardware.  We believe that our implementation will enable the use of the Fr\'echetdistance under translation in applications, whereas previous approaches wouldhave been computationally infeasible.

When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fr\'echet Distance under Translation