Antisocial Planiteers

Antisocial Planiteers

On a spherical planet (I.e. something mathematically neater than Earth) live a collection of aliens who want to live as far away from each other as possible. How should they position their houses so that the minimum distance between any of them is as large as possible?

For n=1 the lone inhabitant can live wherever they want because the problem is symmetrical.

41hgmRkb6iL._SX344_BO1,204,203,200_.jpg

For n=2 the two inhabitants can nest themselves at the antipodes of each other, so at each of the poles as one of the solutions. Again there is redundancy because the first alien in all of these cases can be placed wherever you want.

For three aliens it may not be as obvious. Notice that the greedy algorithm of placing one alien at a time each maximising the distance doesn't work. So if you place two aliens at the poles the third can be placed anywhere along the equator, but this is suboptimal. Instead if you place all three on the equator, each a third of the way along the circumference you get the best separation possible.

For n=4 the best way is to imagine a tetrahedron fitting snuggly inside a sphere as below. Each of the aliens can be placed at one of the vertices:

982px-Вписанный_тетраэдр.svg.png

This method solves all of the cases of the Platonic Solids. So n=4, 6, 8, 12 and 20. These are the only super symmetrical solutions that can exist. From this point on things are going to get messy.

 I usually call hexahedrons by another name, but whatever.

I usually call hexahedrons by another name, but whatever.

For n=5 the best solution is the one you are probably thinking of, although proving that something irregular doesn't do better is tricky. Placing one alien at each pole and then the others around the equator works, but trying to do the same for n=7 is suboptimal because the points on the equator are too bunched up with empty space in both hemispheres. Notice that we skipped the n=6 case because it had a Platonic solution.

From here on the cases are all irregular and while we have solved the first dozen or so exactly, the higher ones are all open problems which we only have computer approximations for.

 Here's the best case for n=7. The picture on the right is the one you want.

Here's the best case for n=7. The picture on the right is the one you want.

If you want to look further this it is called the Tammes Problem, but here's a graph showing the long term behaviour of the solutions. Imagine we draw circles around each of the points such as the diagram above then find the ratio of the total area of all of the circles compared with the surface area of the sphere. Want we is as much of the surface covered as possible.

 Above n=12 It is just conjecture, but we have bounds.

Above n=12 It is just conjecture, but we have bounds.

 

 

Steiner Trees

Steiner Trees

The Twins of Cândido Godói

The Twins of Cândido Godói