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

DOI10.1145/2582112.2582155zbMATH Open1395.68290arXiv1310.5245OpenAlexW1983449524MaRDI QIDQ4635562FDOQ4635562

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

Publication date: 23 April 2018

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

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.

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)

Cited In (6)

• On the Chain Pair Simplification Problem
• 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
• The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
• Title not available (Why is that?)

Recommendations

• COMPUTING THE DISCRETE FRÉCHET DISTANCE WITH IMPRECISE INPUT 👍 👎
• Computing the Discrete Fréchet Distance in Subquadratic Time 👍 👎
• Approximability of the discrete Fréchet distance 👍 👎
• Computing the Discrete Fréchet Distance with Imprecise Input 👍 👎
• Algorithms for the discrete Fréchet distance under translation 👍 👎
• An improved approximation algorithm for the discrete Fréchet distance 👍 👎
• The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection 👍 👎
• Discrete Fréchet Distance under Translation 👍 👎
• Title not available (Why is that?) 👍 👎

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)