Finding maximally far away points

Question

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?

Answer 1

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.