A least sized partition of a set under a distance metric What is the worst case complexity of an algorithm to find a least partition of a set under a distance metric, described as follows:

Input: 


A set $S=\{s_1,\ldots,s_n\}$, where the elements $s_i$ are of some type $T$.  
A distance metric $D:T\rightarrow [0, \infty)$.  
A radius $r:[0, \infty)$


Output: A partition $S_1,\ldots,S_m$ of $S$ such that 


$S_i\cap S_j=\emptyset, i\neq j$ and 
$S=\cup_{i=1}^m S_i$ and
$D(s,t) \leq r$, $s,t \in S_i$ and
There is no other partition with the same properties of size $m^{\prime} &lt; m$.


NOTE: I am saying "a partition" not "the partition", because there may be multiple partitions of least size for the same set of points.  For example consider $2 n$ points on a large circle where the points are spaced such that each pair of points is distance $r$ apart.  In this case there are $2 n-1$ distinct least-sized partitions of minimum size $n$.

NOTE: The following algorithm will produce a partition with desired properties except that it is not guaranteed to be least size:


$i=1$
While $|S| &gt; 0$:


Choose $e \in S$ and set $S:=S-\{e\}$
$S_i=\{x\in S: D(e,x) \leq r\}$
Set $S:=S \setminus S_i$
Set $i:=i+1$



NOTE: It has been suggested that this is an NP-hard problem, but the above partial solution is $O(n^2)$.

NOTE: This problem is an abstraction of this geographic problem.
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