Constant Approximation of Fr'echet Distance in Near-Linear Time
cs.CG
Submitted: 2026-10-30
Updated: 2026-11-03
Code: https://github.com/openai/math
Terminology
Sources
- Edit Distance in Near-Linear Time: it's a Constant Factor
- A faster algorithm for the Fr'echet distance in 1D for the imbalanced case
- The Quick Dog Jumps the Log
- Improved approximation for Fr'echet distance on c-packed curves matching conditional lower bounds
- Fr'echet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability
- Fr'echet Distance in the Imbalanced Case
- SETH Says: Weak Fr'echet Distance is Faster, but only if it is Continuous and in One Dimension
- Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
- Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
- Fr'echet Distance in Subquadratic Time
- Constant Approximation of Fr'echet Distance in Strongly Subquadratic Time
- Approximating the Fr'echet Distance for Realistic Curves in Near Linear Time
- $(5+\epsilon)$-Approximation of Fr'echet Distance in Strongly Subquadratic Time
- A Strongly-Subquadratic $(3+\varepsilon)$-Approximation for the Fr'echet Distance for Paths in Metric Spaces
- A Subquadratic $n^\epsilon$-approximation for the Continuous Fr'echet Distance
- Faster Fr'echet Distance Approximation through Truncated Smoothing
Related papers
- The Rhythm of the Tiles: Narrow and Low Temperature Computation and Simulation in Synchronous Tile Self-Assembly
- k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs
- Covering Points with Rectangular Boundaries
- Tiling 3D Space by (Translates of) a Single Polycube is Undecidable
- Quadratic Complexity of Voronoi Diagrams in R cubed for Lines in a Single Ruling of a Regulus
- Minimum central circles: chain order, seam obstructions, and exact finite certification