Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

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

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.

Item is

Basisdaten

einblenden: ausblenden:
Genre: Forschungspapier
Latex : When {L}ipschitz Walks Your Dog: {A}lgorithm Engineering of the Discrete {F}r\'{e}chet Distance Under Translation

Dateien

einblenden: Dateien
ausblenden: Dateien
:
arXiv:2008.07510.pdf (Preprint), 2MB
Name:
arXiv:2008.07510.pdf
Beschreibung:
File downloaded from arXiv at 2020-10-07 12:17 A shorter version was accepted at ESA 2020
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Bringmann, Karl1, Autor           
Künnemann, Marvin1, Autor           
Nusser, André1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: Computer Science, Computational Geometry, cs.CG,Computer Science, Data Structures and Algorithms, cs.DS
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2020-08-172020
 Publikationsstatus: Online veröffentlicht
 Seiten: 26 p.
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: arXiv: 2008.07510
BibTex Citekey: Bringmann_arXiv2008.07510
URI: https://arxiv.org/abs/2008.07510
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: