When you place points on a plane and measure the Manhattan distance for each point to its closest other point, what is the maximum average distance you can get for $n$ points?
For example, if we have $2$ points on a $15 * 15$ plane, we can place both points in opposite corners and have a distance of $15 + 15$ for both points to the other, thus an average distance of $15$. This is the maximum value we can get, and hence it is the maximum average distance for $2$ points.
The cases where $2 \leq n \leq 5$ are visualized here. It seems that for the first few rounds, we simply divide the circumference by the number of points (i.e. the maximum average distance is $\frac{60}{n}$). For $n = 5$ however, we gain a free place to put a point.
My questions:
- What is the formula behind this?
- How does this translate to higher dimensions?
- How do we continue placing points such that the average distance is maximum?