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

DOI10.1145/2582112.2582155MaRDI QIDQ4635562zbMATH OpenOpenAlexFDO

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

Publication date 23 April 2018

Published in Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

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

zbMATH Keywords

outliersshortcutsgeometric optimizationcurve matchingdiscrete Fréchet distanceapproximate distance selection and counting

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: The emph{Fr'echet distance} is a well studied similarity measures between curves. The emph{discrete Fr'echet distance} is an analogous similarity measure, defined for a sequence $A$ of $m$ points and a sequence $B$ of $n$ points, where the points are usually sampled from input curves. In this paper we consider a variant, called the emph{discrete Fr'echet distance with shortcuts}, which captures the similarity between (sampled) curves in the presence of outliers. For the emph{two-sided} case, where shortcuts are allowed in both curves, we give an $O((m^{2/3}{n}^{2/3}+m+n)lo{g}^3(m+n))$-time algorithm for computing this distance. When shortcuts are allowed only in one noise-containing curve, we give an even faster randomized algorithm that runs in $O((m+n{)}^{6/5+varepsilon})$ expected time, for any $varepsilon>0$. Our techniques are novel and may find further applications. One of the main new technical results is: Given two sets of points $A$ and $B$ and an interval $I$, we develop an algorithm that decides whether the number of pairs $(x,y)inAimesB$ whose distance $mdist(x,y)$ is in $I$, is less than some given threshold $L$. The running time of this algorithm decreases as $L$ increases. In case there are more than $L$ pairs of points whose distance is in $I$, we can get a small sample of pairs that contains a pair at approximate median distance (i.e., we can approximately "bisect" $I$). We combine this procedure with additional ideas to search, with a small overhead, for the optimal one-sided Fr'echet distance with shortcuts, using a very fast decision procedure. We also show how to apply this technique for approximating distance selection (with respect to rank), and for computing the semi-continuous Fr'echet distance with one-sided shortcuts.

Recommendations

• The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
• Approximability of the discrete Fréchet distance
• Approximability of the discrete Fréchet distance
• An improved approximation algorithm for the discrete Fréchet distance
• Computing the discrete Fréchet distance with imprecise input
• Computing the discrete Fréchet distance with imprecise input
• Discrete Fréchet Distance under Translation
• Algorithms for the discrete Fréchet distance under translation

Cited in

(12)

• On the Chain Pair Simplification Problem
• Locality-sensitive hashing of curves
• Fréchet distance between a line and avatar point set
• Approximability of the discrete Fréchet distance
• Adaptive computation of the discrete Fréchet distance
• SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Computing the Fréchet distance with shortcuts is NP-hard
• The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
• Algorithms for the discrete Fréchet distance under translation
• scientific article; zbMATH DE number 7238975 (Why is no real title available?)

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

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