Return to Question

The Maximum Minimum Diversity Problem (MMDP) can be roughly stated as follows:

Let $S$ be a set of points, $k \in \mathbb{N}$. Find the $k$-element subset $M$ of $S$ such that the minimal distance $d_M=\min_{x,y\in M, x\neq y} d(x,y)$ between two points in $M$ is maximal (see e.g. this paper for more details).

As far as I've been able to find, in practical applications $S$ will usually be a (finite) cloud of points, from which $k$ points have to be picked in the most efficient manner possible. My question instead is:

Are there efficient algorithms for directly constructing the set $M$ when $S$ is the $n$-dimensional hypercube (or $n$-orthotope)? Both exact and approximate solutions would be helpful.

P.S. As I'm sure one can notice from the post, I'm not a professional mathematician but I thought the question might still be adequate for this forum. Please feel free to edit for notation etc., add tags or move the question somewhere else if this is not the appropriate place.

The Maximum Minimum Diversity Problem (MMDP) can be roughly stated as follows:

Let $S$ be a set of points, $k \in \mathbb{N}$. Find the $k$-element subset $M$ of $S$ such that the minimal distance $d_M=\min_{x,y\in M, x\neq y} d(x,y)$ between two points in $M$ is maximal (see e.g. this paper for more details).

As far as I've been able to find, in practical applications $S$ will usually be a (finite) cloud of discrete points, from which $k$ points have to be picked in the most efficient manner possible. My question instead is:

Are there efficient algorithms for directly constructing the set $M$ when $S$ is the $n$-dimensional hypercube (or $n$-orthotope)? Both exact and approximate solutions would be helpful.

P.S. As I'm sure one can notice from the post, I'm not a professional mathematician but I thought the question might still be adequate for this forum. Please feel free to edit for notation etc., add tags or move the question somewhere else if this is not the appropriate place.

The Maximum Minimum Diversity Problem (MMDP) can be roughly stated as follows:

Let $S$ be a set of points, $k \in \mathbb{N}$. Find the $k$-element subset $M$ of $S$ such that the minimal distance $d_M=\min_{x,y\in M, x\neq y} d(x,y)$ between two points in $M$ is maximal (see e.g. this paper for more details).

As far as I've been able to find, in practical applications $S$ will usually be a (finite) cloud of points, from which $k$ points have to be picked in the most efficient manner possible. My question is:

Are there efficient algorithms for directly constructing this set when $S$ is the $n$-dimensional hypercube (or $n$-orthotope)? Both exact and approximate solutions would be helpful.

P.S. As I'm sure one can notice from the post, I'm not a professional mathematician but I thought the question might still be adequate for this forum. Please feel free to edit for notation etc., add tags or move the question somewhere else if this is not the appropriate place.

The Maximum Minimum Diversity Problem (MMDP) can be roughly stated as follows:

Let $S$ be a set of points, $k \in \mathbb{N}$. Find the $k$-element subset $M$ of $S$ such that the minimal distance $d_M=\min_{x,y\in M, x\neq y} d(x,y)$ between two points in $M$ is maximal (see e.g. this paper for more details).

As far as I've been able to find, in practical applications $S$ will usually be a (finite) cloud of points, from which $k$ points have to be picked in the most efficient manner possible. My question instead is:

Are there efficient algorithms for directly constructing the set $M$ when $S$ is the $n$-dimensional hypercube (or $n$-orthotope)? Both exact and approximate solutions would be helpful.

P.S. As I'm sure one can notice from the post, I'm not a professional mathematician but I thought the question might still be adequate for this forum. Please feel free to edit for notation etc., add tags or move the question somewhere else if this is not the appropriate place.