## Friday, December 29, 2017

### Maximally Separated Points on a Sphere

One of the designs for a seven-sided die is a sphere truncated at 7 points as far apart from each other as possible. The die doesn't have opposite and parallel sides so there isn't a face for writing the result on. Still the technique is general and could be used to create dice with anywhere between 5 and 100 sides.

How do we find points as far apart as possible from each other? For most values of n the problem is hard. One approach is to sum the pairwise distances of the points and use gradient ascent to find a maximum. The objective function is not convex and has local maxima, but if you think a local maximum is better than nothing, here is code find one. The code uses Euclidean distance, though I wonder if using the angle between two points would work better.  The partial derivatives are with respect to the θ and φ of spherical coordinates since we are constrained to the surface of the sphere.

Running the code:
``````
\$ ./maximally_separated_points_on_sphere.py -n 7``````
``````  (0.139, -0.576, -0.805)
(-0.191, 0.963, 0.191)
(-0.608, 0.338, -0.718)
(0.173, 0.142, 0.975)
(0.884, 0.38, -0.273)
(-0.855, -0.418, 0.308)
(0.458, -0.828, 0.322)
31.530926
``````

The output contains the coordinates of the 7 points found and the value of the objective function at those points.  A convex polytope can be defined in polymake using a set of points—in which case it finds the convex hull—or a set of half spaces—in which case it finds the intersection. Polymake requires homogeneous coordinates.

``````  \$ polymake
polytope > \$p = new Polytope(POINTS =>
[[1, 0.139, -0.576, -0.805],
[1, -0.191, 0.963, 0.191],
[1, -0.608, 0.338, -0.718],
[1, 0.173, 0.142, 0.975],
[1, 0.884, 0.38, -0.273],
[1, -0.855, -0.418, 0.308],
[1, 0.458, -0.828, 0.322]]);

polytope > print \$p->VERTICES_IN_FACETS;``````
``````  {1 2 5}
{0 2 5}
{0 2 4}
{1 3 5}
{1 3 4}
{1 2 4}
{3 4 6}
{3 5 6}
{0 5 6}
{0 4 6}
``````

Polymake tells us the polyhedron has ten faces. This website says there are 5 topologically different polyhedra with 7 vertices and 10 faces. Since polymake tells us which vertices belong to which faces, we can use Blender to visualize the polyhedron.

Following the instructions above yields this picture:
Our polyhedron is topologically equivalent to a pentagonal bipyramid. The figure is the dual of the 7-sided polyhedron we would like to make a die out of. The dual can be found in polymake using polarize:
``````
polytope > \$dual = polarize(\$p);

polytope > print convert_to<Float>(``````
``````    dehomogenize(\$dual->VERTICES));
1.455537382 -0.7147719412 -0.1762669144
1.083809015 0.804520317 0.8537214292
-0.4415750134 -0.506366941 1.52830861
1.059871785 -0.6049596605 -1.125593382
-0.8893855532 -1.073711966 -0.7114555899
-0.2646212759 -1.291044842 1.009076016
-1.423698754 0.1131924589 -0.7895112253
0.2939932965 0.9002156047 -1.208914314
0.4841557507 1.557693116 0.211262627
-1.274046573 0.7045065006 0.518151282

polytope > print \$dual->VERTICES_IN_FACETS;
{1 2 8 9}
{0 3 4 5}
{0 1 2 5}
{3 4 6 7}
{2 4 5 6 9}
{0 1 3 7 8}
{6 7 8 9}
``````

Polymake lists the vertices in a face in ascending order. Blender requires that we list the vertices in the order they occur as we travel around the polygon—otherwise the wireframe will have extra edges in the faces. Trial and error was used to find the correct order:
The polyhedron is topologically equivalent to a pentagonal prism.