2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Lee Nov 9 '16 at 18:15
2
$\begingroup$

I can't access the paper itself, but judging by its abstract and a mention on p. 5 of this paper, a slight generalisation of your problem was proved NP-hard in 1978: Complete-Link Cluster Analysis by Graph Coloring (Pierre Hansen and Michel Delattre). I say "slight generalisation" because (I assume that) the problem proved hard allows arbitrary distances between points; it's possible that Euclidean version of the problem, which you seem to have, is easier. Maybe even the metric version is easier.

For the case of exactly 2 clusters, Wikipedia gives a poly-time algorithm based on 2SAT.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.