I am trying to solve a packing problem in discrete geometry and it would be useful to know the answer to the following problem.

Let $A_1$, $A_2$,..., $A_n$ be $n$ points in the Euclidean plane $\mathbb{R}^2$. Suppose that $A_iA_j\ge 1$ for all $1\le i<j\le n$, where $A_iA_j$ denotes the Euclidean distance between $A_i$ and $A_j$. We say such a point set is $separated$.

Consider the following quantities

$$f(n)=\min \sum_{1\le i<j\le n} A_iA_j^2,\quad \text{and} \quad g(n)=\min \sum_{1\le i<j\le n} A_iA_j.$$ Here the minimums are taken over all separated point sets in the plane.

It is obvious that $f(2)=g(2)=1$ and $f(3)=g(3)=3$. How about $f(4)$ and $g(4)$? I believe $f(4)=8$ and $g(4)=5+\sqrt{3}$ but I cannot prove any of these. What happens for $n=5, 6, 7\ldots$?

Has this problem been considered before? I found some references for the dual $maximization$ problem, when the points are at distance $at \,\, most$ $1$ from each other, but nothing for this problem.

Any help would be greatly appreciated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.