Choosing a subset to maximize the minimum distance between points

Problem Detail: 

I have a set of points $C$, and I have the distance between each point $D(P_i,P_j)$. These distances are euclidean but the points are actually in a feature space.

From the $C$ points I want to choose a subset of $n$ points. Call this subset $s$. I want to choose this subset so as to maximize the minimum distance between all the points in the new set $s$.

$$ \max_{\substack{s \subset C \\ |s| = n}} \left( \min_{\substack{i,j \in s \\ i \neq j} } D \left( P_i, P_j \right) \right) $$

Right now I am using hill climbing to solve this problem. I understand that simulated annealing may give a better solution.

Is there a known solution to this type of problem? Or can this problem be reformulated into another problem that is easily solved?

Asked By : user1389800

Answered By : D.W.

The decision problem version of this optimization problem is:

Given a threshold $t$, you want to know whether it is possible to find a subset of $n$ points such that every pair of points in the subset are at least $t$ units apart.

Of course, if you can solve the decision problem, we can solve your optimization problem (by binary search on the threshold $t$).

Now this decision problem is the problem of finding an independent set in a Euclidean graph, where points $x,y$ have an edge between them if they are at distance $\le t$ apart. One approach would be to look at standard approximation algorithms for independent set.

Even better, you can look at algorithms for independent set in geometric intersection graphs. Consider a set of disks, where each disk has diameter $t$ and is centered at one of the points in your set $C$. Now we can form a geometric intersection graph, where there is one vertex for each disk and an edge between two vertices if their corresponding discs intersect. The problem of finding an independent set in this sort of graph has been studied and there are approximation algorithms for this problem that you could try using.

If you want the exact optimum rather than an approximation, you could use any of the standard "big hammers", such as a SAT solver or an ILP solver. There is a straightforward way to formulate the independent set problem as a SAT instance, and then you could apply a SAT solver to it to find whether there exists a subset of $n$ points which are all $\ge t$ units away from each other.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22767