  Motivated by an application from geodesy, we introduce a novel clustering
problem which is a $k$-center (or k-diameter) problem with a side constraint.
For the side constraint, we are given an undirected connectivity graph $G$ on
the input points, and a clustering is now only feasible if every cluster
induces a connected subgraph in $G$. We call the resulting problems the
connected $k$-center problem and the connected $k$-diameter problem.
  We prove several results on the complexity and approximability of these
problems. Our main result is an $O(\log^2{k})$-approximation algorithm for the
connected $k$-center and the connected $k$-diameter problem. For Euclidean
metrics and metrics with constant doubling dimension, the approximation factor
of this algorithm improves to $O(1)$. We also consider the special cases that
the connectivity graph is a line or a tree. For the line we give optimal
polynomial-time algorithms and for the case that the connectivity graph is a
tree, we either give an optimal polynomial-time algorithm or a
$2$-approximation algorithm for all variants of our model. We complement our
upper bounds by several lower bounds.
