Skip to main content
added 1 character in body
Source Link
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

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>{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.

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.

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.

Source Link
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

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.