  We study the complexity of clustering curves under $k$-median and $k$-center
objectives in the metric space of the Fr\'echet distance and related distance
measures. Building upon recent hardness results for the minimum-enclosing-ball
problem under the Fr\'echet distance, we show that also the $1$-median problem
is NP-hard. Furthermore, we show that the $1$-median problem is W[1]-hard with
the number of curves as parameter. We show this under the discrete and
continuous Fr\'echet and Dynamic Time Warping (DTW) distance. This yields an
independent proof of an earlier result by Bulteau et al. from 2018 for a
variant of DTW that uses squared distances, where the new proof is both simpler
and more general. On the positive side, we give approximation algorithms for
problem variants where the center curve may have complexity at most $\ell$
under the discrete Fr\'echet distance. In particular, for fixed $k,\ell$ and
$\varepsilon$, we give $(1+\varepsilon)$-approximation algorithms for the
$(k,\ell)$-median and $(k,\ell)$-center objectives and a polynomial-time exact
algorithm for the $(k,\ell)$-center objective.
