# Maximum average Manhattan distance to nearest neighbor

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:

1. What is the formula behind this?
2. How does this translate to higher dimensions?
3. How do we continue placing points such that the average distance is maximum?

I believe your question is related to packing, e.g.,

van Dam, Edwin R. "Two-dimensional minimax Latin hypercube designs." Discrete Applied Mathematics 156, no. 18 (2008): 3483-3493. Journal link.

Fig.4 (detail).