Runtime of the optimal greedy $2$-approximation algorithm for the $k$-clustering problem
The problem can be indeed viewed geometrically in a way that we would like to cover the $V$ points by $k$ balls, where the radius of the largest ball is minimized. 

$O(nk)$ is indeed quite simple to achieve but one can do better. Feder and Greene, Optimal algorithms for approximate clustering, 1988 achieve a running time of $\Theta(n \log k)$ using more clever data structures and further show that this is optimal in the algebraic decision tree model.