  Given a trajectory $T$ and a distance $\Delta$, we wish to find a set $C$ of
curves of complexity at most $\ell$, such that we can cover $T$ with subcurves
that each are within Fr\'echet distance $\Delta$ to at least one curve in $C$.
We call $C$ an $(\ell,\Delta)$-clustering and aim to find an
$(\ell,\Delta)$-clustering of minimum cardinality. This problem variant was
introduced by Akitaya $et$ $al.$ (2021) and shown to be NP-complete. The main
focus has therefore been on bicriterial approximation algorithms, allowing for
the clustering to be an $(\ell, \Theta(\Delta))$-clustering of roughly optimal
size.
  We present algorithms that construct $(\ell,4\Delta)$-clusterings of
$\mathcal{O}(k \log n)$ size, where $k$ is the size of the optimal $(\ell,
\Delta)$-clustering. We use $\mathcal{O}(n \log^2 n + n \cdot (k + \ell) \log
n)$ space and $\mathcal{O}(k n^3 \log^4 n)$ time. Our algorithms significantly
improve upon the clustering quality (improving the approximation factor in
$\Delta$) and size (whenever $\ell \in \Omega(\log n)$). We offer deterministic
running times comparable to known expected bounds. Additionally, we give a
near-quadratic improvement upon the dependency on $n$ in the space usage.
