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

DOI10.4230/LIPICS.ESA.2020.25MaRDI QIDQ5874493zbMATH OpenOpenAlexFDO

Authors Karl Bringmann, Marvin Künnemann, André Nusser

Publication date 7 February 2023

Full work available at URL https://arxiv.org/abs/2008.07510

zbMATH Keywords

continuous optimizationcomputational geometryalgorithm engineeringFréchet distance

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• scientific article; zbMATH DE number 1689042 (Why is no real title available?)
• scientific article; zbMATH DE number 2185644 (Why is no real title available?)
• scientific article; zbMATH DE number 1312984 (Why is no real title available?)
• scientific article; zbMATH DE number 7051233 (Why is no real title available?)
• scientific article; zbMATH DE number 757681 (Why is no real title available?)
• scientific article; zbMATH DE number 914364 (Why is no real title available?)
• A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization
• An algorithm for finding the absolute extremum of a function
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Approximately matching polygonal curves with respect to the Fréchet distance
• Approximating the Fréchet distance for realistic curves in near linear time
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Distance measures for point sets and their computation
• FRESH: Fréchet similarity with hashing
• Four Soviets walk the dog: improved bounds for computing the Fréchet distance
• Fréchet distance under translation: conditional hardness and an algorithm via offline dynamic grid reachability
• On the convergence of global methods in multiextremal optimization
• Precision, complexity, and computational schemes of the cubic algorithms
• SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
• The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
• The cubic algorithm
• The fast cubic algorithm
• Two alternatives for the cubic algorithm

Cited in

(3)

• scientific article; zbMATH DE number 7238975 (Why is no real title available?)
• Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
• scientific article; zbMATH DE number 7650283 (Why is no real title available?)

Describes a project that uses

Uses Software

• CGAL
• 2D Arrangement

This page was built for publication: When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874493)