2025/10/17 by van der Horst, Thijs, van Kreveld, Marc, Ophelders, Tim +1
paper · doi:10.20382/jocg.v16i2a9
The Fréchet distance is a commonly used distance measure for curves. Computing the Fréchet distance between two polygonal curves of n vertices takes roughly quadratic time, and conditional lower bounds suggest that approximating to within a factor 3 cannot be done in strongly-subquadratic time, even in one dimension. Currently, one of the best approximation algorithms presents a trade-off between approximation quality and running time. Specifically, at SoCG 2021, Colombe and Fox presented an O((n3 / α2) log n)-time α-approximate algorithm for curves in arbitrary dimensions, for any α ∈ [√(n), n]. In this work, we give an α-approximate algorithm with a significantly faster running time of O((n2 / α) log n), for any α ∈ [1, n]. In particular, we give the first strongly-subquadratic nε-approximation algorithm, for any constant ε ∈ (0, 1/2]. For curves in one dimension we further improve the running time to O((n2 / α3) log2 n), for α ∈ [1, n1/3]. Both of our algorithms rely on a linear-time simplification procedure that in one dimension reduces the complexity of the reachable free space to O(n2 / α) without making sacrifices in the asymptotic approximation factor.