0
$\begingroup$

given a 3d cube with a size of m x m x m, is there an efficient algorithm to find N integer points with the average Euclidean distance between each pair maximized? If not, is there any evolutionary approach I can take to this, so in each step the solution will be improved?

Thanks!

$\endgroup$
  • $\begingroup$ You'll get a pretty good solution if you choose $N$ points at random. $\endgroup$ – Yuval Filmus May 9 at 9:04
1
$\begingroup$

Note that maximizing the average distance between every pair of points is the same as maximizing the total distance between every pair of points.

Let's look at an m x m square first. When N = 4, it is clear that the optimal solution is placing a point in each corner.

For N = 5, the next picture explores two alternatives of placing the 5th point when the other 4 are in the corners. It appears it is optimal to place the 5th point also in a corner. Note that in the right picture, which is already sub-optimal, the total solution does not improve when moving any of the other four points (which are in the corners).

solution in a square

This solution does not work for all N, but it generalizes to cubes when N is a multiple of 8. Then all points are in the eight corners in an optimal solution.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 1. For 5 points, it appears you are assuming that it is optimal to place 4 of the points in a corner. What if there is a better solution that does not involve having at least 4 points in a corner? 2. For cubes, you propose a solution when $N$ is a multiple of 8. How do you know that it is optimal, and that there is no better solution? $\endgroup$ – D.W. May 9 at 21:29
  • $\begingroup$ @D.W. I agree these "proofs" are sloppy, but I challenge anyone to find a counterexample to the claims. Indeed, in 2d for N=5 it is optimal to place all points in corners. In 2d it may only not hold for N = 3 mod 4. And in 3d when N is a multiple of 8, it is optimal to place all points in corners. $\endgroup$ – Albert Hendriks May 10 at 6:44

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.