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

DOI10.4230/LIPICS.ESA.2020.25OpenAlexW3082387026MaRDI QIDQ5874493FDOQ5874493

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Computing the Discrete Fréchet Distance in Subquadratic Time
• Approximately matching polygonal curves with respect to the Fréchet distance
• Approximating the Fréchet distance for realistic curves in near linear time
• Distance measures for point sets and their computation
• An algorithm for finding the absolute extremum of a function
• A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization
• On the convergence of global methods in multiextremal optimization
• The cubic algorithm
• Precision, complexity, and computational schemes of the cubic algorithms
• The fast cubic algorithm
• Two alternatives for the cubic algorithm
• Four Soviets walk the dog: improved bounds for computing the Fréchet distance
• The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
• Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability
• SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
• FRESH: Fréchet similarity with hashing

Cited In (3)

• Title not available (Why is that?)
• Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
• Title not available (Why is that?)

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)