7
$\begingroup$

I consider points in the two-dimensional plane.

An equilateral triangle is a set of three points in the plane which are equidistant.

Suppose now I have $n$ points $x_1,...,x_n$. What is the configuration which minimizes: $$H(x):=\sum_{i,j} (a-\|x_i-x_j\|^2)^2$$ where $a$ is positive real number.

Clearly, if $n=3$, one recovers the equilateral triangle. Could you draw the solution for larger $n$ ? What is the value of $H_{min}$ as a function of $n$?

Thanks!

$\endgroup$
2
  • 6
    $\begingroup$ This is the problem of determing where to place the explosives around the core of an atom bomb, to most efficiently trigger the reaction. It's a classical problem with a substantial literature. Have you looked into it? Generally the minima is not known but in dimension three there's certainly a lot known. In higher dimensions there's quite a bit known for low numbers of points, but again it gets difficult to large numbers of points. $\endgroup$ Mar 5, 2013 at 19:08
  • $\begingroup$ @Ryan Budney : Thanks a lot for this idea. Could you give me a reference ? $\endgroup$
    – user16215
    Mar 6, 2013 at 7:38

1 Answer 1

10
$\begingroup$

First, let's assume $a=1$; for other values we can scale a solution with $\sqrt{a}$.

So we want to minimize $H=\sum_{i,j} (1-\|x_i-x_j\|^2)^2$.

I globally optimized the problem numerically for $n=4$ and $n=5$ and obtained as solutions

for $n=4$, the square with side length $\sqrt{\frac{2}{3}}\approx0.8165$, giving $H_4=\frac{2}{3}$

n=4

for $n=5$, the regular pentagon with side length $\sqrt{\frac{5-\sqrt{5}}{6}}\approx0.6787$, giving $H_5=\frac{5}{3}$

n=5

So in these cases the "generalizations of the equilateral triangle" are the regular polygons. This might be an indication that the regular polygons could be solutions to the optimization problem for other $n$. In any case the regular polygon yields an upper bound. To find the value of $H$ for the regular polygon one just has to find the optimal side length and then plug in the values. Perhaps surprisingly, $H^{C_n}$ takes a particular simple form: $$H^{C_n}=\frac{n(n-3)}{6}.$$ So we know $H^n_{min}\leq H^{C_n}$ and this bound is sharp for $n\in \{3,4,5\}$.

For larger $n$, there are different solutions that obtain the same minimum as the regular polygon. For example distributing the points evenly on the vertices of the equilateral triangle gives $$H=\left\lfloor\frac{\binom{n-1}{2}}{3}\right\rfloor,$$ which is the same as $H^{C_n}$ above if $n$ is a multiple of $3$.

Let me give you two pictures of solutions that are not the regular $n$-gons, but obtain the same minimum:

for $n=6$:

n=6

for $n=7$:

n=7

I think minimizing this function is interesting also in dimensions other than $d=2$, even $d=1$, but mainly $d>2$. Maybe one can exploit the symmetry in the polynomial $H$ in some way. I don't know the references and the connection to explosives that Ryan Budney mentions in his comment.

$\endgroup$
2
  • $\begingroup$ Great, thank you for this nice work. Any idea about a sharp solution? $\endgroup$
    – user16215
    Sep 25, 2014 at 12:07
  • $\begingroup$ @user16215 not at the moment.. $\endgroup$ Sep 25, 2014 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.