  In a geometric $k$-clustering problem the goal is to partition a set of
points in $\mathbb{R}^d$ into $k$ subsets such that a certain cost function of
the clustering is minimized. We present data structures for orthogonal
range-clustering queries on a point set $S$: given a query box $Q$ and an
integer $k>2$, compute an optimal $k$-clustering for $S\setminus Q$. We obtain
the following results. We present a general method to compute a
$(1+\epsilon)$-approximation to a range-clustering query, where $\epsilon>0$ is
a parameter that can be specified as part of the query. Our method applies to a
large class of clustering problems, including $k$-center clustering in any
$L_p$-metric and a variant of $k$-center clustering where the goal is to
minimize the sum (instead of maximum) of the cluster sizes. We extend our
method to deal with capacitated $k$-clustering problems, where each of the
clusters should not contain more than a given number of points. For the special
cases of rectilinear $k$-center clustering in $\mathbb{R}^1$, and in
$\mathbb{R}^2$ for $k=2$ or 3, we present data structures that answer
range-clustering queries exactly.
