  The Fr\'echet distance is a popular distance measure for curves. We study the
problem of clustering time series under the Fr\'echet distance. In particular,
we give $(1+\varepsilon)$-approximation algorithms for variations of the
following problem with parameters $k$ and $\ell$. Given $n$ univariate time
series $P$, each of complexity at most $m$, we find $k$ time series, not
necessarily from $P$, which we call \emph{cluster centers} and which each have
complexity at most $\ell$, such that (a) the maximum distance of an element of
$P$ to its nearest cluster center or (b) the sum of these distances is
minimized. Our algorithms have running time near-linear in the input size for
constant $\varepsilon$, $k$ and $\ell$. To the best of our knowledge, our
algorithms are the first clustering algorithms for the Fr\'echet distance which
achieve an approximation factor of $(1+\varepsilon)$ or better.
  Keywords: time series, longitudinal data, functional data, clustering,
Fr\'echet distance, dynamic time warping, approximation algorithms.
