Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
4  
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. –  Ryan Budney Mar 5 '13 at 19:08
    
@Ryan Budney : Thanks a lot for this idea. Could you give me a reference ? –  user16215 Mar 6 '13 at 7:38

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.