2
$\begingroup$

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?
$\endgroup$

1 Answer 1

1
$\begingroup$

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).


$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .