A least sized partition of a set under a distance metric
Ken Supowit proved that the following problem is NP-hard: Given a set $P$ of $n$ points in the Euclidean plane and an integer $k$, partition $P$ into $k$ clusters so that the largest cluster diameter is minimized.


  Kenneth J Supowit: "Topics in Computational Geometry"
  Ph.D. thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign (1981), Report UIUCDCS-R-81-1062


Tomás Feder and Dan Greene proved that even the problem of approximating the smallest possible cluster diameter within a factor of $1.97$ is NP-hard.


  T Feder, D.H Greene: "Optimal algorithms for approximate clustering"
  Proceedings of the 20th Annual ACM Symposium on the Theory Computing (1988), pp. 434-444