# Algorithm for MaxMin diversity problem on hypercube?

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.

• Are you interested in the continuous hypercube or the discrete set $\{0,1 \}^N$ with $N$ large is also Ok? – RaphaelB4 Jan 24 at 18:07
• I'm interested in the continuous hypercube, thanks for asking. – leopold.talirz Jan 24 at 20:15
• As a first approximation (for k large with respect to n) take p smallest with p^n greater than or equal to k. Then arrange the k points in an array of p^n points. This will give you an immediate lower bound and arrangement. For n large, one can do better, but one can structure the better solutions by looking at optimal packing of d points where d^n is bigger than k, and then make an array (or fractal) of scaled down solutions. Gerhard "So Take Nth Roots First" Paseman, 2019.01.24. – Gerhard Paseman Jan 24 at 21:36

For a large number of points $$k$$ and $$S$$ a hypercube, a good approximate answer can be given by referring to the sphere packing literature (see for instance Conway and Sloane's book Sphere Packings, Lattices and Groups and online databases such as Nebe and Sloane's Lattices page, or Scholl's Sphere Packing Database among other sources). Here one can construct roughly optimal $$M$$ by taking all lattice points in the hypercube from an appropriately scaled lattice. For low dimensions it is conjectured that the optimal sphere packing density is attained for a lattice packing (where each sphere has as radius half the distance from the closest vector to the origin in the lattice) which has been verified for dimensions $$d=2,3,8,$$ and $$24$$, but for dimensions even as small as $$d=10$$ there are non-lattice packings denser than any known lattice packings (for more information on this see Elkies' survey here from the AMS Notices, although more recent developments answer some of the questions posed there).
For general $$k$$, to give exact solutions (even in two-dimensions!) may be very difficult. A related problem is of finding best packings of circles of the same radius in a unit square (a simple observation, as by rescaling, to any maximal distance set $$M$$ with all distances appearing being at least $$d<1$$, all circles of radius $$d$$ centered at the $$k$$ points in $$M$$ must fit inside the square of length $$1+2d$$ and be non-overlapping). Several recent papers on this problem appear from M. Locatelli and P. Szabó and their co-authors (see here, here, section two in the first link gives a few equivalents of this problem, one of which is the problem posed in the question). Packomania is a great resource to check best known configurations for particular numbers of points.