14
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I'm interested in a similar problem. Based on my until now searching results, it's comparable to the p-dispersion problem in facility location problem for which This is a nice review paper. $\endgroup$
    – XTZ
    Aug 8, 2018 at 23:46
  • $\begingroup$ Do you know what's the name of this problem? $\endgroup$
    – Dandelion
    Jan 3, 2019 at 16:40

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ In case it's useful for anyone, I've implemented the solution from DW in Python, using an approximation algorithm for independent sets from networkx. $\endgroup$
    – pjet
    Feb 2 at 12:03
2
$\begingroup$

This problem is known as the MaxMin Diversity Problem (MMDP). It is known to be NP-hard. However, there are algorithms for giving good approximate solutions in reasonable time, such as this one.

I'm answering this question years after it was asked because I was looking for algorithms to solve the same problem, and had trouble even finding out what to call it.

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