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$?
$\begingroup$
$\endgroup$
3
-
$\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 PasemanCommented Dec 8, 2015 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$– HalbortCommented Dec 8, 2015 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 PasemanCommented Dec 8, 2015 at 16:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
14
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.
answered Dec 8, 2015 at 18:05
-
$\begingroup$ For $n = 4$, if you make an equilateral triangle with one point in the center I think you get $4\sqrt{3}$ $\endgroup$– HalbortCommented Dec 8, 2015 at 18:20
-
1$\begingroup$ @Halbort: I get it to be $16/\sqrt{3}$... $\endgroup$ Commented Dec 8, 2015 at 18:32
-
$\begingroup$ I just realized that I messed up. $\endgroup$– HalbortCommented Dec 8, 2015 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$ Commented Dec 8, 2015 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$ Commented Dec 8, 2015 at 19:48