The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection

DOI10.1145/2700222zbMath1398.68609OpenAlexW1967985699MaRDI QIDQ4962190

Omrit Filtser, Rinat Ben-Avraham, Haim Kaplan, Micha Sharir, Matthew J. Katz

Publication date: 30 October 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2700222

zbMATH Keywords

outliersshortcutsgeometric optimizationcurve matchingdiscrete Fréchet distanceapproximate distance selection and counting

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)

Related Items (5)

Rearranging a sequence of points onto a line ⋮ Reverse shortest path problem in weighted unit-disk graphs ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance ⋮ When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation ⋮ Computing the Fréchet gap distance

This page was built for publication: The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection