  The Fr\'echet distance is a popular distance measure for curves. Computing
the Fr\'echet distance between two polygonal curves of $n$ vertices takes
roughly quadratic time, and conditional lower bounds suggest that even
approximating to within a factor $3$ cannot be done in strongly-subquadratic
time, even in one dimension. The current best approximation algorithms present
trade-offs between approximation quality and running time. Recently, van der
Horst $\textit{et al.}$ (SODA, 2023) presented an $O((n^2 / \alpha) \log^3 n)$
time $\alpha$-approximate algorithm for curves in arbitrary dimensions, for any
$\alpha \in [1, n]$. Our main contribution is an approximation algorithm for
curves in one dimension, with a significantly faster running time of $O(n
\log^3 n + (n^2 / \alpha^3) \log^2 n \log \log n)$. Additionally, we give an
algorithm for curves in arbitrary dimensions that improves upon the
state-of-the-art running time by a logarithmic factor, to $O((n^2 / \alpha)
\log^2 n)$. 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(n^2 / \alpha)$ without making sacrifices in the asymptotic
approximation factor.
