Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
Computing the distance between two sets (say two curves) is a problem appearing in different applicable situations. One possibility is using the Hausdorff distance. This paper deals with a different distance, namely Fréchet distance, between plane curves. This distance, also called dogleash-distance, is defined as the minimum length of a leash required to connect a dog and its owner as they walk without backtracking along their respective curves from one endpoint to the other; in the introduction of the paper the authors quote some references for illustrating the applicability of this type of distance. In this paper, the authors present a generalization of the Fréchet distance requiring continuity on the motion of the leash. In addition, they present a polynomial time algorithm for computing this generalized distance between two polygonal curves in the plane minus a set of polygonal obstacles.
- Fréchet Distance for Curves, Revisited
- Tightness and computing distances in the curve complex
- On the decidability of the Fréchet distance between surfaces
- Homotopic distance between maps
- Folding free-space diagrams: computing the Fréchet distance between 1-dimensional curves
- Determining the Hausdorff distance between trees in polynomial time
- Gromov-Fréchet distance between curves
- Efficient geodesics and an effective algorithm for distance in the complex of curves
- Approximating the Hausdorff distance by \(\alpha\)-dense curves
- scientific article; zbMATH DE number 176499
- A new data structure for shortest path queries in a simple polygon
- An Optimal Algorithm for Euclidean Shortest Paths in the Plane
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Computing homotopic shortest paths efficiently
- Computing minimum length paths of a given homotopy class
- COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
- Constrained Delaunay triangulations
- Euclidean shortest paths in the presence of rectilinear barriers
- Fréchet Distance for Curves, Revisited
- Geodesic Fréchet distance inside a simple polygon
- scientific article; zbMATH DE number 1262422 (Why is no real title available?)
- scientific article; zbMATH DE number 2079391 (Why is no real title available?)
- scientific article; zbMATH DE number 1461253 (Why is no real title available?)
- LATIN 2004: Theoretical Informatics
- Minimal tangent visibility graphs
- New similarity measures between polylines with applications to morphing and polygon sweeping
- Optimal shortest path queries in a simple polygon
- Parallel Merge Sort
- Parametric search made practical
- Slowing down sorting networks to obtain faster sorting algorithms
- Testing homotopy for paths in the plane
- The nature and meaning of perturbations in geometric computing
- Two problems concerning Fréchet distance and lines of evasion
- Constructing monotone homotopies and sweepouts
- Measuring and improving the geometric accuracy of piece-wise polynomial boundary meshes
- Median trajectories
- Four Soviets walk the dog: improved bounds for computing the Fréchet distance
- Computing the Fréchet distance between polygons with holes
- Fréchet distance problems in weighted regions
- Walking your dog in the woods in polynomial time
- Fréchet distance problems in weighted regions
- scientific article; zbMATH DE number 1189312 (Why is no real title available?)
- Tighter connections between Formula-SAT and shaving logs
- Computing optimal homotopies over a spiked plane with polygonal boundary
- Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
- scientific article; zbMATH DE number 7650283 (Why is no real title available?)
- How to walk your dog in the mountains with no magic leash
- Fréchet distance with speed limits
- How to walk your dog in the mountains with no magic leash
- Revisiting the Fréchet distance between piecewise smooth curves
- The geodesic Fréchet distance between two curves bounding a simple polygon
This page was built for publication: Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1037652)
