# Minimum number of sets of points

During my work I've encountered this problem:

$G = \{(x_i,y_i,z_i)\}_{i=1}^{n}$ is a group of points in space ($\forall i \;\; x_i,y_i,z_i \in \Bbb R$) and $d \in \Bbb R^+$ is a constant.

Divide $G$ to $m$ groups (as few as possible) that follow this rule: for each pair of points in the same group, the distance between these two points is less than or equal to $d$. ($m$ should be, as said, the minimum)

I thought about solving it by turning it into a graph where each point is a node and 2 nodes are connected if and only if the distance between these 2 points is smaller than $d$. Then the solution is the same as finding a minimal cover of the graph using Cliques. This is an NP problem and thus can't be solved in polynomial time unless P=NP. So that doesn't provide a useful solution.

Does anybody have any idea how to solve this problem?

• How necessary is it that you find the minimum cliques? It sort of feels like there's some greedyish $(\epsilon, \delta)$ approximation scheme that relies on expanding out the maximal cliques from some random permutation of the points. In fact, if you have some prior distribution of the points (say that you know that there's probably a logarithmic number of cliques with respect to the number of points), running the greedy algorithm some polynomial number of times should also give a reasonably-tight approximation as well. – Lee Nov 9 '16 at 18:15