5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you interested in the continuous hypercube or the discrete set $\{0,1 \}^N$ with $N$ large is also Ok? $\endgroup$ – RaphaelB4 Jan 24 at 18:07
  • $\begingroup$ I'm interested in the continuous hypercube, thanks for asking. $\endgroup$ – leopold.talirz Jan 24 at 20:15
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Jan 24 at 21:36
1
$\begingroup$

There is a very large literature on such problems which involve finding configurations which maximize the minimum distance over all fixed sized point sets in some compact metric space.

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.

For numerical solutions which aim to be exact, many calculations of the large configurations rely on use of stochastic optimization techniques (finally, these can be found in a list of references for the constructions which appear on the packomania webpage).

$\endgroup$
  • $\begingroup$ Since I was interested more in the general case (k not necessarily large), I found your Locatelli & Szabó references particularly useful. I'll wait a little more before accepting this as the answer. $\endgroup$ – leopold.talirz Jan 24 at 23:08
  • $\begingroup$ 'Diversity' is not a term oft used to describe these types of problems. It is possible this question might have been answered quicker if it had been phrased slightly differently. $\endgroup$ – Josiah Park Jan 24 at 23:15
  • $\begingroup$ One question of clarification: You explain how the sphere-packing problem and the maxmin problem are related but section 2 of this reference states that they are equivalent(?). Can I get the maxmin solution from a densest packing of spheres? $\endgroup$ – leopold.talirz Jan 24 at 23:26
  • $\begingroup$ Yes. The two are equivalent. The initial answer began to give an argument for why so, but later a reference was found for it. To clarify, your problem is equivalent to packing identical (hyper)spheres in a (hyper)cube. $\endgroup$ – Josiah Park Jan 24 at 23:32

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.