Four Soviets walk the dog: improved bounds for computing the Fréchet distance
From MaRDI portal
Publication:2408191
DOI10.1007/s00454-017-9878-7zbMath1379.68319arXiv1209.4403OpenAlexW2588820692WikidataQ59528497 ScholiaQ59528497MaRDI QIDQ2408191
Wouter Meulemans, Kevin Buchin, Wolfgang Mulzer, Maike Buchin
Publication date: 10 October 2017
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1209.4403
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)
Related Items
Locally correct Fréchet matchings ⋮ Translation invariant Fréchet distance queries ⋮ Fréchet Distance for Uncertain Curves ⋮ Unnamed Item ⋮ When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation ⋮ Computing the Fréchet distance between uncertain curves in one dimension ⋮ Approximating the Packedness of Polygonal Curves ⋮ Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance ⋮ Computing the Fréchet distance between uncertain curves in one dimension ⋮ Fast Fréchet Distance Between Curves with Long Edges ⋮ Fréchet distance between two point sets ⋮ Approximating the packedness of polygonal curves
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing the Fréchet distance with a retractable leash
- Approximating the Fréchet distance for realistic curves in near linear time
- Necklaces, convolutions, and \(X+Y\)
- Fréchet distance with speed limits
- Near-linear time approximation algorithms for curve simplification
- Can we compute the similarity between surfaces?
- Computing the Fréchet distance between simple polygons
- Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
- On a circle placement problem
- How good is the information theory bound in sorting?
- Surpassing the information theoretic bound with fusion trees
- Improved parallel integer sorting without concurrent writing
- Locally correct Fréchet matchings
- New similarity measures between polylines with applications to morphing and polygon sweeping
- Comparison of distance measures for planar curves
- On a class of \(O(n^ 2)\) problems in computational geometry
- Fast Fréchet queries
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
- Subquadratic algorithms for 3SUM
- Towards polynomial lower bounds for dynamic problems
- Approximability of the discrete Fréchet distance
- Delaunay triangulations in O (sort( n )) time and more
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- DETECTING COMMUTING PATTERNS BY CLUSTERING SUBTRAJECTORIES
- Improved Algorithms for Partial Curve Matching
- Geodesic Fréchet distance inside a simple polygon
- A MATHEMATICAL THEORY OF ADAPTIVE CONTROL PROCESSES
- Parity, circuits, and the polynomial-time hierarchy
- Fréchet Distance of Surfaces: Some Simple Hard Cases
- The Computational Geometry of Comparing Shapes
- Computing connected components on parallel computers
- Storage Modification Machines
- Efficiency of a Good But Not Linear Set Union Algorithm
- An Expander-Based Approach to Geometric Optimization
- Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations
- Approximate nearest neighbor algorithms for Frechet distance via product metrics
- Threesomes, Degenerates, and Love Triangles
- COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
- The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
- Computing the Fréchet Distance between Folded Polygons
- Computational Complexity
- Jaywalking Your Dog: Computing the Fréchet Distance with Shortcuts
- The frechet distance revisited and extended
- On Range Searching with Semialgebraic Sets. II
- Fréchet Distance for Curves, Revisited
- Computing the Discrete Fréchet Distance in Subquadratic Time
- Lower bounds for linear degeneracy testing
