Four Soviets walk the dog: improved bounds for computing the Fréchet distance
From MaRDI portal
Publication:2408191
Abstract: Given two polygonal curves in the plane, there are many ways to define a notion of similarity between them. One popular measure is the Fr'echet distance. Since it was proposed by Alt and Godau in 1992, many variants and extensions have been studied. Nonetheless, even more than 20 years later, the original algorithm by Alt and Godau for computing the Fr'echet distance remains the state of the art (here, denotes the number of edges on each curve). This has led Helmut Alt to conjecture that the associated decision problem is 3SUM-hard. In recent work, Agarwal et al. show how to break the quadratic barrier for the discrete version of the Fr'echet distance, where one considers sequences of points instead of polygonal curves. Building on their work, we give a randomized algorithm to compute the Fr'echet distance between two polygonal curves in time on a pointer machine and in time on a word RAM. Furthermore, we show that there exists an algebraic decision tree for the decision problem of depth , for some . We believe that this reveals an intriguing new aspect of this well-studied problem. Finally, we show how to obtain the first subquadratic algorithm for computing the weak Fr'echet distance on a word RAM.
Recommendations
Cites work
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- scientific article; zbMATH DE number 176499 (Why is no real title available?)
- scientific article; zbMATH DE number 3637287 (Why is no real title available?)
- scientific article; zbMATH DE number 1351079 (Why is no real title available?)
- scientific article; zbMATH DE number 732977 (Why is no real title available?)
- scientific article; zbMATH DE number 7051233 (Why is no real title available?)
- A MATHEMATICAL THEORY OF ADAPTIVE CONTROL PROCESSES
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
- An Expander-Based Approach to Geometric Optimization
- Approximability of the discrete Fréchet distance
- Approximate nearest neighbor algorithms for Frechet distance via product metrics
- Approximating the Fréchet distance for realistic curves in near linear time
- COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
- Can we compute the similarity between surfaces?
- Comparison of distance measures for planar curves
- Computational Complexity
- Computing connected components on parallel computers
- Computing the Fréchet distance between folded polygons
- Computing the Fréchet distance between simple polygons
- Computing the Fréchet distance with a retractable leash
- Delaunay triangulations in O (sort( n )) time and more
- Detecting commuting patterns by clustering subtrajectories
- Efficiency of a Good But Not Linear Set Union Algorithm
- Fast Fréchet queries
- Fréchet Distance for Curves, Revisited
- Fréchet distance of surfaces: some simple hard cases
- Fréchet distance with speed limits
- Geodesic Fréchet distance inside a simple polygon
- Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
- How good is the information theory bound in sorting?
- Improved algorithms for partial curve matching
- Improved parallel integer sorting without concurrent writing
- Jaywalking your dog: computing the Fréchet distance with shortcuts
- Lower bounds for linear degeneracy testing
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- Near-linear time approximation algorithms for curve simplification
- Necklaces, convolutions, and \(X+Y\)
- New similarity measures between polylines with applications to morphing and polygon sweeping
- On a circle placement problem
- On a class of \(O(n^ 2)\) problems in computational geometry
- On range searching with semialgebraic sets. II.
- Parity, circuits, and the polynomial-time hierarchy
- Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations
- Storage Modification Machines
- Subquadratic algorithms for 3SUM
- Surpassing the information theoretic bound with fusion trees
- The Computational Geometry of Comparing Shapes
- The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
- Threesomes, degenerates, and love triangles
- Towards polynomial lower bounds for dynamic problems
Cited in
(17)- scientific article; zbMATH DE number 7650283 (Why is no real title available?)
- Approximating the packedness of polygonal curves
- Approximability of the discrete Fréchet distance
- When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation
- \((1+\varepsilon)\)-ANN data structure for curves via subspaces of bounded doubling dimension
- Walking your dog in the woods in polynomial time
- Translation invariant Fréchet distance queries
- Fréchet Distance for Uncertain Curves
- Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
- Fast Fréchet distance between curves with long edges
- Computing the Fréchet distance between uncertain curves in one dimension
- Fréchet distance between two point sets
- Computing the Fréchet distance between uncertain curves in one dimension
- Computing the Fréchet distance with a retractable leash
- Four Soviets walk the dog -- with an application to Alt's conjecture
- Walking the dog fast in practice: algorithm engineering of the Fréchet distance
- Approximating the Packedness of Polygonal Curves
This page was built for publication: Four Soviets walk the dog: improved bounds for computing the Fréchet distance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2408191)
