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

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