  We give the first near-linear time $(1+\eps)$-approximation algorithm for
$k$-median clustering of polygonal trajectories under the discrete Fr\'{e}chet
distance, and the first polynomial time $(1+\eps)$-approximation algorithm for
$k$-median clustering of finite point sets under the Hausdorff distance,
provided the cluster centers, ambient dimension, and $k$ are bounded by a
constant. The main technique is a general framework for solving clustering
problems where the cluster centers are restricted to come from a \emph{simpler}
metric space. We precisely characterize conditions on the simpler metric space
of the cluster centers that allow faster $(1+\eps)$-approximations for the
$k$-median problem. We also show that the $k$-median problem under Hausdorff
distance is \textsc{NP-Hard}.
