Before revision:  More specifically, we show an deterministic algorithm that finds for any set P \subseteq R^d of n points and any k \in \{2, \dots, n\} in O(nd \log k ) time a partition of P into k subsets such that there is a ball of radius O ( \left( k{n}diam(P) ) \right) intersecting the convex hull of each subset.
After revision:  More specifically, we show an deterministic algorithm that finds for any set P \subseteq R^d of n points and any k \in \{2, \dots, n\} in O(nd \log k ) time a partition of P into k subsets such that there is a ball of radius O \left( k{n}diam(P) ) \right) intersecting the convex hull of each subset.