2026/07/07 by Lenny Liu, Jihan Wang
#cs.CG
We give randomized (5+ε)-approximation algorithms for both the continuous and discrete Fréchet distances on arbitrary two polygonal curves τ and σ in \mathbb Rd for fixed d, with n and m≤ n vertices respectively. Our algorithm for continuous Fréchet runs in \widetilde Od,ε(n m8/9) time, and our algorithm for discrete Fréchet runs in \widetilde Od,ε(n m4/5) time. These bounds improve the recent strongly subquadratic constant-factor approximation algorithms of Cheng, Huang, and Zhang~\citecheng2025constant, which give (7+ε)-approximations. The approximation improvement comes from certifying long boundary-to-boundary reachability directly through auxiliary surrogate curves, avoiding an extra conversion back to input subcurves and hence removing one triangle-inequality loss. The running-time improvement comes from a two-scale macro-surrogate search combined with dyadic auxiliary-transfer structures, with the discrete case gaining a faster bound from exact planar reachability in the discrete free-space graph.