Finding maximally far away points
-
29-09-2020 - |
Frage
Given a metric space $X$ with finitely many points, and a nonnegative integer $n$, I want to find a set of $n$ points in $X$ which maximizes the minimum distance between any two points.
What algorithms are there to do this?
Lösung
The problem is NP-hard, by reduction from independent set.
If you have an undirected graph, treat the distance between two vertices $v,w$ to be $2$ if there is an edge $(v,w) \in E$, or $1$ if not. There there is an independent set of size $n$ in this graph iff there is a set of $n$ points whose minimum distance is 2.
So, your best bet is probably to use some algorithm for independent set (maybe a SAT solver, or maybe something else), combined with a binary search on the minimum distance.
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange