10
$\begingroup$

Suppose we have $n$ points on a plane. Let $D$ be the sum of the squares of all the pairwise distances between the points. Let $A$ be the area of the convex hull. What is the minimum possible value of $\frac{D}{A}$ and what arrangement achieves it for specific values of $n$?

$\endgroup$
  • $\begingroup$ I would think n=3 achieves the minimum, by looking at convex polygons and noting they have many diagonals. Probably one can show the equilateral triangle is optimal. Gerhard "Try Thinking In The Small" Paseman, 2015.12.07. $\endgroup$ – Gerhard Paseman Dec 8 '15 at 6:10
  • $\begingroup$ @GerhardPaseman I had meant to find the minimum value for each value of $n$ not to find the value of $n$ which achieves the minimum. By the way, it is pretty easy to prove that equilateral triangle is optimal for $n = 3$. $\endgroup$ – Halbort Dec 8 '15 at 16:44
  • $\begingroup$ Then try dividing n into three groups, and arrange the groups in the form of an equilateral triangle. I suspect that will do better than most arrangements. Gerhard "Triangles Can Be Pretty Useful" Paseman, 2015.12.08 $\endgroup$ – Gerhard Paseman Dec 8 '15 at 16:55
6
$\begingroup$

I conjecture that the minimum is $2n$, for all $n\geq 4$. This is obtained by putting four points in a square and the remaining points in the center.

There are then $(n-4)$ vertices in the center, and thus the total sum of distances squared is $4 \cdot \frac{1}{2}(n-4) + 4 + 2\cdot 2= 2n$, assuming that the square has area $1$.

I ran many simulations using a genetic algorithm (here is the mathematica code):

Needs["ComputationalGeometry`"];

Mutate[ptList_,f_:0.1]:=ptList + f*RandomReal[{-1,1},{Length@ptList,2}];

Fitness[ptList_]:=Fitness[ptList]=Module[{aa,dd},
    aa=ConvexHullArea[ptList];
    dd=Total[(EuclideanDistance@@@Subsets[ptList,{2}])^2];
    dd/aa
];

RunSimulation[ptsLists_]:=Module[{newLists,j=1},
    newLists=ptsLists;

    Do[
        newLists[[k]] = Mutate[newLists[[j++]],0.01];
    ,{k,Ceiling[Length[newLists]/2],Length[newLists]}];

    newLists=SortBy[newLists,Fitness];

    gg=ListPlot[ newLists[[1]], Axes->False,PlotStyle->{PointSize[0.02]},
PlotLabel->("Fitness: " <>ToString@Fitness@newLists[[1]]),Frame->True,
AspectRatio->Automatic,FrameTicks->False ];

    newLists
];

Clear[gg]
Print[Dynamic[gg]];

init=RandomReal[{0,1},{100,9,2}];
pts=SortBy[init,Fitness];

Do[
pts=RunSimulation[pts];
,{1800}];

This code above runs 1800 generations with 100 lists, each with 9 points. However, looks like a pentagon with the remaining points in the middle is a local minima, so one has to restart a few times to see the square.

$\endgroup$
  • $\begingroup$ For $n = 4$, if you make an equilateral triangle with one point in the center I think you get $4\sqrt{3}$ $\endgroup$ – Halbort Dec 8 '15 at 18:20
  • 1
    $\begingroup$ @Halbort: I get it to be $16/\sqrt{3}$... $\endgroup$ – Per Alexandersson Dec 8 '15 at 18:32
  • $\begingroup$ I just realized that I messed up. $\endgroup$ – Halbort Dec 8 '15 at 18:40
  • 2
    $\begingroup$ It should be not too hard to show minimality by abstractly pushing dots around. Things inside the convex hull should gravitate toward a centroid, and points not too far outside the convex hull of the remaining points should be absorbable when there are at least 4 remaining points. Gerhard "Hand Waving Gives Some Elevation" Paseman, 2015.12.08 $\endgroup$ – Gerhard Paseman Dec 8 '15 at 19:46
  • $\begingroup$ @GerhardPaseman: Yes, but I think you will find that a regular n-gon, with the remaining dots in the center is a local minima... Perhaps one can argue that the ONLY local minima are of this form, and then it is easy to find which of these is global. $\endgroup$ – Per Alexandersson Dec 8 '15 at 19:48

Your Answer

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

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