Given a $d$-dimensional rectangle ("hyper-rectangle"?)
$$A = [0,n_1]\times[0,n_2]\times\dots\times[0,n_d]$$
with $n_1,\dots,n_d\in\mathbb{R}^+$
How to fill it with $k$ points homogeneously? Or alternatively, where to place the $k$ points such that the minimum distance between any two points is maximal?
This turned out to be a surprisingly difficult question to answer. I started scribbling, and the solution wasn't even obvious in $d=2$ dimensions, for example for $k=5$.
The solution was sometimes to have $4$ points in the corner of the rectangle and $1$ in the center; and sometimes, if the rectangle was really narrow, to have them in a line along the rectangles longer side, alternating their positions.
Similarly, here are some solutions for $d=3, k=9$, for a cube-like and narrow a cuboid:
I think "optimal sphere packing" is a large part of this, because we're technically packing hyper-spheres of an unknown radius $R$ to fill up $A$ perfectly.
I have tried solving it using Operations Research, specifically Quadratic Optimization. Let's call the variables $x_1,\dots,x_k\in\mathbb{R}^d$, with $x_{im}$ being the $m$'th coordinate of the $i'th$ variable. Then the optimization problem is:
$$\begin{align}&\max{R} \\ \text{s.t.}\qquad &\forall i \in \{0,\dots,k\}:\quad x_i \ge 0\\ &\forall i \in \{0,\dots,k\}\quad\forall m \in \{0,\dots,d\}:\quad x_{im} \le n_m\\ &\forall i \in \{0,\dots,k\}\quad\forall j \in \{i+1,\dots,k\}:\quad ||x_i - x_j||_2^2 \ge R^2 \\ \end{align}$$
Where the first two sets of conditions ensure that the points are in $A$, and the third set of conditions ensure that each pair of points is at least distance $R$ away from each other. In the optimal sphere packing, each "neighbouring" point will be exactly distance $R$ away, and every other point will be distance $\ge R$ away from each other.
Of course, since $R > 0$, the objective is equivalent to $\max{R^2}$. However the problem is still quadratic because of the $||x_i - x_j||_2^2$ terms.
I have tried solving this optimization problem for small cases, namely $d=2$ and $n$ is some small whole number with the Lagrange multiplier method, however, the issue quickly gets quite large.
Since if $X = (x_1,\dots,x_k)$ is a solution, then any reordering of $X$ is also a solution; it might be smart to also use some kind of ordering condition, like $x_{1j} \le x_{2j} \le \dots \le x_{dj}$ for some $j$, although this might lead to infeasibility.
Maybe there is also another way to solve this problem, with some kind of smart insight.
