  Subtrajectory clustering is an important variant of the trajectory clustering
problem, where the start and endpoints of trajectory patterns within the
collected trajectory data are not known in advance. We study this problem in
the form of a set cover problem for a given polygonal curve: find the smallest
number $k$ of representative curves such that any point on the input curve is
contained in a subcurve that has Fr\'echet distance at most a given $\Delta$ to
a representative curve. We focus on the case where the representative curves
are line segments and approach this NP-hard problem with classical techniques
from the area of geometric set cover: we use a variant of the multiplicative
weights update method which was first suggested by Br\"onniman and Goodrich for
set cover instances with small VC-dimension. We obtain a
bicriteria-approximation algorithm that computes a set of $O(k\log(k))$ line
segments that cover a given polygonal curve of $n$ vertices under Fr\'echet
distance at most $O(\Delta)$. We show that the algorithm runs in
$\widetilde{O}(k^2 n + k n^3)$ time in expectation and uses $ \widetilde{O}(k n
+ n^3)$ space. For two dimensional input curves that are $c$-packed, we bound
the expected running time by $\widetilde{O}(k^2 c^2 n)$ and the space by $
\widetilde{O}(kn + c^2 n)$. In $\mathbb{R}^d$ the dependency on $n$ instead is
quadratic. In addition, we present a variant of the algorithm that uses
implicit weight updates on the candidate set and thereby achieves near-linear
running time in $n$ without any assumptions on the input curve, while keeping
the same approximation bounds. This comes at the expense of a small
(polylogarithmic) dependency on the relative arclength.
