Suppose, we have a region (say, for simplicity, a unit cube) and a distance function that, given the coordinates of any two points in the region, calculates the distance between them. It is not simply the Euclidean distance, and it is not invariant with respect to translations and rotations of a pair of points, but it is continuous, positive, bounded above by $1$, and obeys the triangle inequality. It doesn't have a closed-form expression in terms of elementary and special functions known to Mathematica, and can only be evaluated numerically with machine precision.

We need to select $N$ (where $1<N<30$) points from the region so that the closest pair of points among them are as far apart as possible. In other words, we need to maximize the smallest pairwise distance among all the selected points. Ideally, in case there are multiple configurations of points with the same smallest distance, then we would like to also maximize the second (third, and so on) smallest distance. We are okay with the relative numerical error of the calculated coordinates to be $10^{-4}$ or below. We can assume that the distance function will not result in too narrow local maxima (i.e. local maxima that can be discovered only if the accuracy of the coordinates is better than $10^{-4}$).

What's the best approach to solving this problem?

  • 2
    $\begingroup$ Please post a concrete example by Mathematica code. $\endgroup$
    – cvgmt
    Apr 16 at 23:31
  • $\begingroup$ I'd use NMaximize with objective function defined by FindMinimum or, if the distance function is too persnickety, NMinimize. $\endgroup$ Apr 17 at 1:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.