Fréchet Distance for Curves, Revisited

DOI10.1007/11841036_8zbMATH Open1131.68561DBLPconf/esa/AronovHKWW06arXiv1504.07685OpenAlexW2153708898WikidataQ61632359 ScholiaQ61632359MaRDI QIDQ5449516FDOQ5449516

Authors: Christian Knauer, Yusu Wang, Carola Wenk, Boris Aronov, Sariel Har-Peled 

Publication date: 11 March 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: $$ We revisit the problem of computing Fr'echet distance between polygonal curves under $L_1$, $L_2$, and $L_{i}nfty$ norms, focusing on discrete Fr'echet distance, where only distance between vertices is considered. We develop efficient algorithms for two natural classes of curves. In particular, given two polygonal curves of $n$ vertices each, a $eps$-approximation of their discrete Fr'echet distance can be computed in roughly $O(nkapp{a}^{3}logn/ep{s}^3)$ time in three dimensions, if one of the curves is emph{$kappa$-bounded}. Previously, only a $kappa$-approximation algorithm was known. If both curves are the so-called emph{�ackbone~curves}, which are widely used to model protein backbones in molecular biology, we can $eps$-approximate their Fr'echet distance in near linear time in two dimensions, and in roughly $O(n^{4/3}lognm)$ time in three dimensions. In the second part, we propose a pseudo--output-sensitive algorithm for computing Fr'echet distance exactly. The complexity of the algorithm is a function of a quantity we call the emph{�wnumber{}}, which is quadratic in the worst case, but tends to be much smaller in practice.

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

Recommendations

• Computing the Fréchet distance with a retractable leash
• Computing the Fréchet distance with a retractable leash
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (53)

• Approximating the Fréchet distance for realistic curves in near linear time
• Approximating the integral Fréchet distance
• Tighter connections between Formula-SAT and shaving logs
• Approximating the packedness of polygonal curves
• Approximation algorithms for geometrical distance problems that are not solvable exactly
• \((1+\varepsilon)\)-ANN data structure for curves via subspaces of bounded doubling dimension
• Four Soviets walk the dog: improved bounds for computing the Fréchet distance
• Fast Fréchet queries
• A middle curve based on discrete Fréchet distance
• Voronoi diagram of polygonal chains under the discrete Fréchet distance
• Probabilistic embeddings of the Fréchet distance
• A sequential algorithm for recognition of a developing pattern with application in orthotic engineering
• On the complexity of range searching among curves
• Distinct distances on curves via rigidity
• Static and streaming data structures for Fréchet distance queries
• A comprehensive study of clustering a class of 2D shapes
• Title not available (Why is that?)
• Voronoi Diagram of Polygonal Chains under the Discrete Fréchet Distance
• Fast Fréchet distance between curves with long edges
• Title not available (Why is that?)
• Go with the flow: the direction-based Fréchet distance of polygonal curves
• Computing the discrete Fréchet distance with imprecise input
• Fréchet distance between a line and avatar point set
• Approximating the Fréchet distance for realistic curves in near linear time
• Recursive Computation of the Fréchet Mean on Non-positively Curved Riemannian Manifolds with Applications
• Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
• Sampling-based bottleneck pathfinding with applications to Fréchet matching
• Shortest path problems on a polyhedral surface
• On the discrete Fréchet distance in a graph
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Approximately matching polygonal curves with respect to the Fréchet distance
• Fréchet distance between two point sets
• Fréchet similarity of closed polygonal curves
• Computing the discrete Fréchet distance with imprecise input
• Discretely following a curve
• Link distance and shortest path problems in the plane
• Computing the Fréchet gap distance
• Computing the Fréchet distance with a retractable leash
• Title not available (Why is that?)
• Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
• Computing the Fréchet distance between polygons with holes
• Computing the Fréchet distance between piecewise smooth curves
• Fréchet distance between a line and avatar point set
• Middle curves based on discrete Fréchet distance
• Folding free-space diagrams: computing the Fréchet distance between 1-dimensional curves
• Universal approximate simplification under the discrete Fréchet distance
• Fréchet distance problems in weighted regions
• Fréchet distance problems in weighted regions
• Chord-to-point distance accumulation and planar curvature: A new approach to discrete curvature
• Integrated shape-sensitive functional metrics
• Approximating the Packedness of Polygonal Curves
• Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
• Title not available (Why is that?)

This page was built for publication: Fréchet Distance for Curves, Revisited

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