A least sized partition of a set under a distance metric

Question

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} < 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| > 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.

Answer 1

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