English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation

MPS-Authors
/persons/resource/persons44182

Bringmann,  Karl
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44857

Künnemann,  Marvin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons228472

Nusser,  André
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)

arXiv:2008.07510.pdf
(Preprint), 2MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Bringmann, K., Künnemann, M., & Nusser, A. (2020). When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation. Retrieved from https://arxiv.org/abs/2008.07510.


Cite as: http://hdl.handle.net/21.11116/0000-0007-2A56-A
Abstract
Consider the natural question of how to measure the similarity of curves in the 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 the curves' shapes rather than their positioning in the plane, e.g., to compare the similarity of handwritten characters. Perhaps the most natural such notion is the (discrete) Fr\'echet distance under translation. Unfortunately, the algorithmic literature on this problem yields a very pessimistic view: On polygonal 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 Strong Exponential Time Hypothesis fails. Can we still obtain an implementation that is efficient on realistic datasets? Spurred by the surprising performance of recent implementations for the Fr\'echet distance, we perform algorithm engineering for the Fr\'echet distance under translation. Our solution combines fast, but inexact tools from continuous optimization (specifically, branch-and-bound algorithms for global Lipschitz optimization) with exact, but expensive algorithms from computational geometry (specifically, problem-specific algorithms based on an arrangement construction). We combine these two ingredients to obtain an exact decision algorithm for the Fr\'echet distance under translation. For the related task of computing the distance value up to a desired precision, we engineer and compare different methods. On a benchmark set involving handwritten characters and route trajectories, our implementation answers a typical query for either task in 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\'echet distance under translation in applications, whereas previous approaches would have been computationally infeasible.